Struktur Data Graph

Graph : struktur data yang berbentuk network/jaringan, hubungan
antar elemen adalah many-to-many

Struktur Data Graph = keterhubungan tak terbatas antara entitas data.
Contoh graph : Informasi topologi jaringan dan keterhubungan antar
kota-kota

Graph terdiri dari himpunan verteks (node) dan himpunan sisi (edge, arc).
Verteks menyatakan entitas-entitas data dan sisi menyatakan
keterhubungan antara verteks.
Notasi matematis graph G adalah :
G = (V, E)

Graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunan
bagian dari V dan E1 himpunan bagian dari E.

Jenis Graph

a. Directed Graph (Digraph) : jika sisi-sisi graph hanya berlaku satu arah.
Misalnya : {x,y} yaitu arah x ke y, bukan dari y ke x; x disebut origin
dan y disebut terminus. Secara notasi sisi digraph ditulis sebagai
vektor (x, y).
Contoh Digraph G = {V, E} :
V = {A, B, C, D, E, F, G, H, I,J, K, L, M}
E = {(A,B),(A,C), (A,D), (A,F), (B,C), (B,H), (C,E), (C,G), (C,H), (C,I), (D,E),
(D,F), (D,G), (D,K), (D,L), (E,F), (G,I), (G,K), (H,I), (I,J), (I,M), (J,K), (J,M),
(L,K), (L,M)}.

b. Graph Tak Berarah (undirected graph atau undigraph): setiap sisi {x, y}
berlaku pada kedua arah: baik x ke y maupun y ke x. Secara grafis sisi
pada undigraph tidak memiliki mata panah dan secara notasional
menggunakan kurung kurawal.
Contoh Undigraph G = {V, E}
V = {A, B, C, D, E, F, G, H, I,J, K, L, M}
E = { {A,B},{A,C}, {A,D}, {A,F}, {B,C}, {B,H}, {C,E}, {C,G}, {C,H}, {C,I}, {D,E},
{D,F}, {D,G}, {D,K}, {D,L}, {E,F}, {G,I}, {G,K}, {H,I}, {I,J}, {I,M}, {J,K},
{J,M}, {L,K}, {L,M}}.

b. Graph Tak Berarah (undirected graph atau undigraph): setiap sisi {x, y}
berlaku pada kedua arah: baik x ke y maupun y ke x. Secara grafis sisi
pada undigraph tidak memiliki mata panah dan secara notasional
menggunakan kurung kurawal.
Contoh Undigraph G = {V, E}
V = {A, B, C, D, E, F, G, H, I,J, K, L, M}
E = { {A,B},{A,C}, {A,D}, {A,F}, {B,C}, {B,H}, {C,E}, {C,G}, {C,H}, {C,I}, {D,E},
{D,F}, {D,G}, {D,K}, {D,L}, {E,F}, {G,I}, {G,K}, {H,I}, {I,J}, {I,M}, {J,K},
{J,M}, {L,K}, {L,M}}.

Konektivitas pada Digraph
Terminologi pada Undigrap berlaku, kecuali dalam digraph harus dikaitkan
dengan arah tertentu karena pada arah yang sebaliknya belum tentu
terdefinisi.
Adjacency ke/dari : Jika ada sisi (x,y) maka pada digraph dikatakan bahwa
x "adjacent ke" y atau y "adjacent dari" x. Demikian pula jika terdapat
path dari x ke y maka belum tentu ada path dari y ke x. Jadi dalam
digraph keterkoneksian didefinisikan lebih lanjut lagi sebagai berikut.
- Terkoneksi Kuat : Bila setiap pasangan verteks berbeda x dan y
dalam S, x berkoneksi dengan y dan y berkoneksi dengan x
- Terkoneksi Lemah : Bila setiap pasangan verteks berbeda x dan y
dalam S, salah satu: x berkoneksi dengan y (atau y berkoneksi
dengan x) dan tidak kebalikan arahnya (hanya terdefinisi satu path:
dari x ke y atau sebaliknya dari y ke x).

Graph berbobot (weighted graph)
Graph dengan sisi mempunyai Bobot/ Biaya. “Biaya" ini bisa mewakili
banyak aspek: biaya ekonomi suatu aktifitas, jarak geografis/tempuh, waktu
tempuh, tingkat kesulitan, dan lain sebagainya.
Contoh :
Graph ini merupakan Undirected Weighted Graph. Order dari verteks A = 4,
verteks B = 3, dst. Adjacentcy list dari D adalah = {A, E, F, G, K, L}.

Representasi Graph
Representasi Matriks Keterhubungan Langsung (Adjacency Matrix)
Matriks digunakan untuk himpunan adjacency setiap verteks. Baris berisi
vertex asal adjacency, sedangkan kolom berisi vertex tujuan adjacency.
Bila sisi graph tidak mempunyai bobot, maka [x, y] adjacency disimbolkan
dengan 1 dan 0 bila tidak adjacency.
Bila sisi graph mempunyai bobot, maka [x, y] adjacency disimbolkan dengan
bobot sisi tersebut, dan bila tidak disimbolka