Graph

Struktur Data Graph

Struktur data yang berbentuk network/jaringan, hubungan antar elemen adalah many-to-many

Keterhubungan dan jarak tidak langsung antara dua kota = data keterhubungan langsung dari kota-kota lainnya yang memperantarainya.Penerapan struktur data linear atau hirarki pada masalah graph dapat dilakukan tetapi kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straightforward) dilakukan pada strukturnya sendiri.

1. Struktur Data Linear = keterhubungan sekuensial antara entitas data

2. Struktur Data Tree = keterhubungan hirarki

3. 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)

Sebuah sisi antara verteks x dan y ditulis {x, y}.

Subgraph : graph yang merupakan suatu subset (bagian) graph yang connected

Graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunanbagian 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 arahx 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}}.

Khusus graph, undigraph bisa sebagai digraph (panah di kedua ujung edge berlawanan) 

Struktur data linear maupun hirarkis adalah juga graph. Node - node pada struktur linear ataupun hirarkis adalah verteks - verteks dalam pengertian graph dengan sisi-sisinya menyusun node-node tersebut secara linear atau hirarkis.

Struktur data linear adalah juga tree dengan pencabangan pada setiap node hanya satu atau tidak ada. Linear single linked list (digraph), linear 2-way linked list (undigraph).