Graph dan implementasi graph dalam struktur data

Graf adalah 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. Agar lebih jelas perhatikan gambar dibawah ini :



Dalam gambar tersebut, terdapat beberapa kota yang berada dipulau jawa dimana kota kota tersebut dihubungkan oleh beberapa jalur jalur yang ada. Untuk contoh diatas kita bisa menganggap bawah kota kota yang ada merupakan vertex, dan jalur jalur yang menghubungkan kota kota tersebut sebagai edge. Sehingga secara keseluruhan peta diatas dapat dibuat pemodelannya sebagai sebuah graf. Ada terdapat beberapa jenis graf yang bisa kita gunakan, yaitu beberapa diantaranya adalah sebagai berikut : ~ Graf Berarah : adalah graf yang edge-nya memiliki arah, sebagai contoh edge AB menghubungkan vertex A ke B, dimana hubungan vertex B ke A, harus diperoleh dari edge lain, yaitu edge BA, dan jika edge BA tidak ada, maka vertex B ke A tidak memiliki hubungan, meski vertex A ke B memiliki hubungan ~ Graf Tak Berarah : adalah graf yang edge-nya tidak memiliki arah, sehigga jika edge AB menghubungkan vertex A ke B, maka secara otomatis juga menghubungkan vertex B ke A. ~ Graf Berbobot : adalah suatu graf dimana edge dari graf tersebut memiliki bobot atau nilai tertentu. ~ Graf Berbobot : adalah suatu graf dimana edge dari graf tersebut tidak memiliki bobot atau nilai.