Graf memodelkan hubungan antar objek, dari peta jalan dan jaringan komputer sampai prasyarat mata kuliah. Modul ini dimulai dari representasi adjacency list dan adjacency matrix, lalu menelusuri grafnya dengan BFS untuk lintasan terpendek tak berbobot dan DFS untuk komponen terhubung serta siklus. Bagian akhir menyusun urutan topologis dengan algoritma Kahn, menjaga keadaan terhubung lewat union-find, dan menutup dengan Dijkstra serta Bellman-Ford pada graf berbobot. Materinya berdiri di atas rekursi, antrian, dan heap yang dibangun pada modul-modul sebelumnya.
Graf
Modul graf: representasi adjacency, BFS, DFS, urutan topologis, union-find, dan lintasan terpendek Dijkstra.
0/0 selesai
- Representasi graf
Adjacency list versus adjacency matrix beserta pembangunan keduanya dari daftar tepi.
- BFS pada graf
Lintasan tak berbobot terpendek dan penelusuran per level dengan antrian.
- DFS pada graf
Pencarian mendalam untuk komponen terhubung dan deteksi siklus.
- Urutan topologis
Pengurutan DAG dengan algoritma Kahn dan DFS beserta keluarga soal jadwal mata kuliah.
- Union-find
Struktur himpunan saling lepas dengan path compression dan union by rank untuk komponen terhubung.
- Lintasan terpendek berbobot
Dijkstra dengan heap dan pengenalan Bellman-Ford untuk graf berbobot negatif.