Apa Itu Graph?

Graf adalah struktur data yang memodelkan sekumpulan hal dan hubungan di antaranya. Hal-hal tersebut disebut simpul (atau node), dan hubungannya disebut sisi.

Graf ada di mana-mana. Jejaring sosial adalah graf (orang adalah simpul, pertemanan adalah sisi). Peta jalan adalah graf (persimpangan adalah simpul, jalan adalah sisi). Internet, pohon dependensi, dan peta permainan juga merupakan graf.

Dalam kursus ini, kita berfokus pada graf tak berarah: jika sebuah sisi menghubungkan u dan v, maka v juga terhubung ke u. Tidak ada arah. Kita akan menggunakan bilangan bulat sebagai kunci simpul agar tetap sederhana.

Secara internal, kita akan menyimpan graf sebagai adjacency list: sebuah map dari setiap simpul ke list tetangganya. Dengan cara ini, kita dapat mencari tetangga sebuah simpul hanya dengan satu akses map, yang dibutuhkan oleh sebagian besar algoritma graf.

Operasi yang akan kita buat pada class Graph adalah:

1. addVertex: Tambahkan simpul baru yang belum memiliki sisi.
2. addEdge: Hubungkan dua simpul.
3. hasEdge: Periksa apakah dua simpul terhubung.
4. getNeighbors: Dapatkan list tetangga sebuah simpul.
5. removeEdge: Putuskan hubungan antara dua simpul.
6. size: Hitung jumlah simpul dalam graf.

Mari kita buat class Graph!