Graph dalam struktur data

April 16, 2010

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 hirarkis pada masalah graph dapat dilakukan tetapi kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straight forward) dilakukan pada strukturnya sendiri. 1.

Struktur Data Linear = keterhubungan sekuensial antara entitas data 2.

Struktur Data Tree = keterhubungan hirarkis 3.

Struktur Data Graph = keterhubungan tak terbatas antara entitas data. Contoh graph :
Informasi topologi jaringan dan keterhubungan antar
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 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}}. 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
ngertian 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 1-way linked list (digraph), linear 2-way linked list (undigraph).

Posted in Uncategorized | Leave a Comment »