Graph

Graph merupakan struktur data yang menyerupai Tree. Jika kita memandang tree dan graph secara matematis, maka kita akan menemukan bahwa tree merupakan bentuk khusus dari graph. Namun karena perbedaan metode implementasi dari graph dan tree, maka kedua kasus ini dipisahkan. Implementasi tree dalam pemrograman lebih menyerupai implementasi linked list, stack, dan queue.
Hal terlihat dari penggunaan pointer untuk membentuk struktur dari data yang ada. Implementasi graph dalam pemrograman tidak menggunakan pointer untuk membentuk struktur graph.

Graph direpresentasikan menggunakan elemen-elemen berikut:

1. Daftar node
   Node yang ada di dalam graph dikumpulkan dalam satu daftar yang memiliki index, agar masingmasing
   node dapat mudah diakses. Daftar ini dapat diimplementasikan menggunakan array,
   atau linked list. Contoh:
   class Node{
   …
   }
   class Graph{
   Node daftarNode[];
   }
2. Kumpulan edge
   Setiap edge menggambarkan hubungan antara dua node yang dihubungkan oleh edge tersebut.
   Dua buah node yang terhubung oleh sebuah edge merupakan node-node yang bertetangga.
   Ketetanggaan antar node digambarkan di dalam sebuah matriks, yang disebut matriks
   ketetanggaan (adjacency matrix).

Representasi data dengan struktur data linear ataupun hirarkis pada masalah ini masih bisa digunakan namun akan membutuhkan pencarian-pencarian yang kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straightforward) dilakukan pada strukturnya sendiri.

Masalah-masalah Graph
Masalah path minimum (Shortest path problem):
mencari route dengan jarak terpendek dalam suatu jaringan transportasi.

Masalah aliran maksimum (maximum flow problem):
menghitung volume aliran BBM dari suatu reservoir ke suatu titik tujuan melalui jaringan pipa.

Masalah pencariah dalam graph (graph searching problem):
mencari langkah-langkah terbaik dalam program permainan catur komputer.

Masalah pengurutan topologis (topological ordering problem):
menentukan urutan pengambilan mata-mata kuliah yang saling berkaitan dalam hubungan prasyarat (prerequisite).

Masalah jaringan tugas (Task Network Problem):
membuat penjadwalan pengerjaan suatu proyek yang memungkinkan waktu penyelesaian tersingkat.

Masalah pencarian pohon rentang minimum (Minimum Spanning Tree Problem):
mencari rentangan kabel listrik yang totalnya adalah minimal untuk menghubungkan sejumlah kota.

Travelling Salesperson Problem:
tukang pos mencari lintasan terpendek melalui semua alamat penerima pos tanpa harus mendatangi suatu tempat lebih dari satu kali.

Four-color problem:
dalam menggambar peta, memberikan warna yang berbeda pada setiap propinsi yang saling bersebelahan.

Definisi
Suatu graph didefinisikan oleh himpunan verteks dan himpunan sisi (edge). Verteks menyatakan entitas-entitas data dan sisi menyatakan keterhubungan antara verteks. Biasanya untuk suatu graph G digunakan notasi matematis
G = (V, E)

V adalah himpunan verteks dan E himpunan sisi yang terdefinisi antara pasangan-pasangan verteks. Sebuah sisi antara verteks x dan y ditulis {x, y}.

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

Digraph & Undigraph

Graph Berarah (directed graph atau digraph): jika sisi-sisi pada graph, misalnya {x, y} hanya berlaku pada arah-arah tertentu saja, yaitu dari x ke y tapi tidak dari y ke x; verteks x disebut origin dan vertex y disebut terminus dari sisi tersebut. Secara grafis maka penggambaran arah sisi-sisi digraph dinyatakan dengan anak panah yang mengarah ke verteks terminus, secara notasional sisi graph berarah ditulis sebagai vektor dengan (x, y).
graph di samping ini adalah suatu contoh Digraph G = {V, E}
dengan V = {A, B, C, D, E, F, G, H, I,J, K, L, M}
dan 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)}.

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.
graph di samping ini adalah suatu contoh Undigraph G = {V, E}
dengan V = {A, B, C, D, E, F, G, H, I,J, K, L, M}
dan 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}}.

Dalam masalah-masalah graph undigraph bisa dipandang sebagai suatu digraph dengan mengganti setiap sisi tak berarahnya dengan dua sisi untuk masing-masing arah yang berlawanan.
Undigraph di atas tersebut bisa dipandang sebagai Digraph G = {V, E}
dengan V = {A, B, C, D, E, F, G, H, I,J, K, L, M}
dan 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,A), (C,A), (D,A), (F,A), (C,B), (H,B), (E,C), (G,C), (H,C), (I,C), (E,D), (F,D), (G,D), (K,D), (L,D), (F,E), (I,G), (K,G), (I,H), (J,I), (M,I), (K,J), (M,J), (K,L), (M,L)}

Selain itu, berdasarkan definisi ini maka struktur data linear maupun hirarkis adalah juga graph. Node-node pada struktur linear atupun hirarkis adalah verteks-verteks dalam pengertian graph dengan sisi-sisinya menyusun node-node tersebut secara linear atau hirarkis. Sementara kita telah ketahui bahwa struktur data linear adalah juga tree dengan pencabangan pada setiap node hanya satu atau tidak ada. Linear 1-way linked list adalah digraph, linear 2-way linked list bisa disebut undigraph.

CONTOH CODING :

HASIL CODING :