graph

Pengrtian graph

Graphs merupakan fundamental struktur data (data structure) didunia programming – sebuah abstrak yang dapat menggambarkan sistem transportasi, electrical circuits, interaksi antara manusia, telekomunikasi jaringan dll. Sangat banyak perbedaan struktur yang dapat di modelkan menggunakan dari sebuah graph.
Nah disini kita hanya fokus pada pengetahuan dasar yang dibutuhkan untuk algoritma graph, khususnya penggunaan tepat dari struktur data graph dan traversal algorithm.


Sebuah graph G = (V,E) dibentuk dari sekumpulan vertices(titik) V, dan sekumpulan edges(penghubung/garis) E seperti pada Gambar 1. Pada pemodelan jalan, vertices bisa menunjukkan kota atau persimpangan jalan, yang tentu saja dihubungkan oleh jalan yang dimodelkan dengan edges. Contoh lain ada pada pemodelan meng-analisa source code pada program komputer, vertice menunjukkan baris kode(lines of code), dengan sebuah edges yang menjadi penghubung antar baris, misal x dan y dimana statement y dieksekusi setelah x.
Ada beberapa properti dasar dari graph yang mempengaruhi pemilihan dari struktur data yang biasa digunakan untuk menggambarkannya dan algoritma yang tersedia utnuk menganalisa graph tersebut. Langkah awal pada setiap persoalan graph ditentukan oleh beberapa pertimbangan, seperti:

* Undirected vs directed – sebuah graph G = (V,E) dikatakan Undirected jika edge (x,y) ? E menyatakan bahwa (y,x) juga ada pada E (Gambar.3). Jika tidak, maka dikatakan directed (Gambar.2). Jalanan antar kota bisa dikatakan undirected, karena jalan besar yang biasa dilewati dengan dua arah, sedangkan jalan2 dalam kota yang satu arah bisa dikatakan directed karena graph tersebut memiliki arah yang sudah ditentukan.




* Weighted vs UnWeighted – pada Weighted graph(Gambar.4), setiap edge(bisa juga verteices) dari graph G diberikan sebuah nilai atau bobot. Biasanya menggambarkan jarak jalan, waktu tempuh antara x dan y. Pada unweihted graph, nilai atau bobot tidak ada atau tidak ada perbedaan nilai atau bobot antara edges atau vertice yang berbeda. Perbedaan antara Weighted dan unWeighted menjadi penting bila digunakan untuk mencari jalur terpendek dari sebuah graph. Untuk unWeighted graph, jalur terpendek harus memiliki beberapa edges, dan dapat dicari dengan menggunakan algoritma breadth-first search(BFS).



* Cyclic vs Acyclic – sebuah graph yang acyclic tidak memiliki cycle yang dapat kembali ke node sebelumnya. Tree(Gambar.5) merupakan acyclic Undirected graph yang terhubung, karena alur dari edge-nya tidak dapat kembali lagi keatas. Cyclic adalah graph yang dapat kembali ke node sebelumnya(Gambar.3).



* Simple vs Non-simple – jika terdapat sebuah self-loop pada edge(x,x) pada satu vertices disebut Non-simple() ( Gambar.6)sedangkan graph yang tidak memunculkan hal tersebut disebut simple



* Implicit vs explicit – banyak graph yang tidak dibentuk sejak awal, yang berarti graph itu dibentuk pada saat kita menggunakannya(di programming di sebut pada saat runtime), contoh lebih dekat untuk graph type implicit ini adalah permainan labirin. Bayangkan kita mencari jalan pada permainan labirin, kita belum tahu jalan mana yang harus dilalui untuk sampai ke tujuan…, nah disini kita membuat graph pada saat kita melewati jalan2 tersebut, nah.. pada saat kita melewati jalan tersebut kita sedang membentuk graph. Sedangkan graph explicit adalah graph yang sudah dibentuk sebelumnya