Graph problem

• Definisi Graph

Graph adalah struktur data yang paling umum. Jika struktur linear memungkinkan pendefinisian keterhubungan sikuensial antara entitas data, struktur data tree memungkinkan pendefinisian keterhubungan hirarkis, maka struktur graph memungkinkan pendefinisian keterhubungan tak terbatas antara entitas data.

Graf Juga merupakan salah satu jenis struktur data yang terdiri dari titik (vertex) dan garis (edge), dimana dalam graf tersebut, vertex - vertex yang ada dihubungkan oleh edge, hingga menjadi suatu kesatuan yang disebut graf. Sebagai contoh dari pemodelan graf adalah peta kota kota, dimana kota disini sebagai vertex dan jalur yang menghubungkannya berlaku sebagai edge.

Lihat Gambar di bawah ini!

Di dalam gambar tersebut, terdapat beberapa kota yang ada dipulau  jawa dimana kota - kota tersebut terhubung oleh beberapa jalur - jalur yang ada. Untuk contoh diatas kita bisa menganggap bawah kota-kota yang ada tersebut  merupakan vertex, dan jalur-jalur yang menghubungkan kota-kota tersebut sebagai edge. Sehingga secara keseluruhan peta diatas dapat dibuat pemodelannya sebagai sebuah graf.

• Merepresentasikan Graph dalam bentuk matriks

-      Graph tak berarah

Graf tersebut dapat direpresentasikan dalam sebuah matrik 5x5 , dimana baris dan kolom di matriks tersebut menunjukan vertex yang ada

-      Graph Berarah

Di dalam matrik diatas kita dapat lihat bahwa kotak yang berisi angka satu  menunjukkan bahwa dalam dua vertex tersebut terdapat edge yang menghubungkannya. Dan jika dalam kotak tersebut terdapat angka nol, maka hal tersebut menunjukkan tidak ada edge yang menguhubungkan secara langsung dua vertex tersebut.

ü                            Untuk representasi dalam pemorgraman komputer, graph  dapat kita gambarkan seperti dibawah ini :

 

ü       

                       Istilah – istilah dalam Graph

1.       Incident

Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w), maka v dan w disebut “terletak” pada e, dan e disebut incident dengan v dan w.

2.       Degree

 Di dalam Graph juga ada yang disebut dengan Degree, Degree mempuyai 3 jenis antara lain :

-          Degree dari suatu verteks x dalam undigraph adalah jumlah busur yang incident dengan simpul tersebut.

-          Indegree dari suatu verteks x dalam digraph adalah jumlah busur yang kepalanya incident dengan simpul tersebut, atau jumlah busur yang “masuk” atau menuju simpul tersebut.

-          Outdegree dari suatu verteks x dalam digraph adalah jumlah busur yang ekornya incident dengan simpul tersebut, atau jumlah busur yang “keluar” atau berasal dari simpul tersebut.

3.      Adjacent

Pada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut. Simpul v dan w disebut adjacent.

 

Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v.

4.      Successor dan Predecessor

Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v adalah successor simpul w, dan simpul w adalah predecessor dari simpul v.

5.      Path

Sebuah path adalah serangkaian simpul-simpul berbeda yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.

• Jenis – Jenis Graph

1.      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. Maka 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)}.

2.      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 juga merupakan graph. Sedangkan 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 1-way linked list (digraph), linear 2- way linked list (undigraph).

• Pengimplementasian Graph pada Java

         Berikut adalah gambar scripnya !

 

Dapat dilihat dari gambar diatas, logika Graph di mulai dari penambahan Vertex/Node, dengan memanggil fungsi “AddVertex” pada file Graph.java. maka Setelah vertex tercipta, dilakukanlah penambahan Edge/Busur dan terakhir memanggil fungsi untuk menghasilkan outputnya.

Berikut adalah gambar outputnya !

Sumber :

link