Penelusuran graf — BFS, DFS, dan Dijkstra

Graf $G = (V, E)$ terdiri dari himpunan simpul (vertex) $V$ dan sisi (edge) $E$. Peta jalan, jaringan pertemanan, dependensi mata kuliah, bahkan grid di game semuanya bisa dimodelkan sebagai graf.

Representasi

	Adjacency matrix	Adjacency list
Memori	$O(V^2)$	$O(V + E)$
Cek apakah $(u, v)$ ada	$O(1)$	$O(\deg u)$
Iterasi tetangga $u$	$O(V)$	$O(\deg u)$
Cocok untuk	graf padat	graf jarang (paling umum)

BFS vs DFS

Breadth-First Search menjelajah melebar: semua tetangga jarak 1, lalu semua jarak 2, dan seterusnya. Memakai queue. Pada graf tak berbobot, BFS menemukan jalur dengan jumlah sisi paling sedikit.

Depth-First Search masuk sedalam mungkin dulu, lalu mundur (backtrack). Memakai stack (atau rekursi). DFS berguna untuk deteksi siklus, topological sort, dan mencari komponen terhubung.

Grid di bawah adalah graf: setiap sel adalah simpul, terhubung ke 4 tetangganya. Bandingkan pola penjelajahannya. Lalu gambar lumpur (biaya 5) dan lihat bedanya BFS (tidak peduli biaya) dengan Dijkstra.

Pencarian jalur di grid

BFSDFSDijkstra / UCS▶ Animasikan

Kuas:■ Tembok≈ Lumpur (biaya 5)□ HapusKosongkanContoh

S

G

Node dijelajahi: 270Panjang jalur: 30Biaya jalur: 50

Uninformed. Menjelajah melebar lapis demi lapis (queue). Optimal jika semua langkah berbiaya sama, tapi buta terhadap lumpur. Klik/seret di grid untuk menggambar.

BFS & DFS pada adjacency list▶ Jalankan

Kompleksitas BFS dan DFS dengan adjacency list: $O(V + E)$. Setiap simpul diproses sekali, setiap sisi diperiksa sekali (dua kali untuk graf tak berarah).

Dijkstra: jalur terpendek berbobot

Kalau sisi punya bobot (jarak, waktu, biaya), jumlah sisi paling sedikit belum tentu jalur termurah. Dijkstra selalu mengambil simpul dengan jarak sementara terkecil dari priority queue, lalu melakukan relaksasi:

$$\text{jika } d[u] + w(u, v) < d[v] \text{ maka } d[v] \leftarrow d[u] + w(u, v)$$

Dengan binary heap, kompleksitasnya $O((V + E)\log V)$.

Cek pemahaman

1. 1. Struktur data inti BFS adalah…

   A.StackB.QueueC.Priority queueD.Hash set saja

2. 2. Pada graf tak berbobot, algoritma mana yang menjamin jumlah sisi minimum dari sumber?

   A.DFSB.BFSC.KeduanyaD.Tidak ada

3. 3. Kompleksitas BFS dengan adjacency matrix?

   A.O(V + E)B.O(V²)C.O(E log V)D.O(V)

Latihan: Jumlah Pulau, Jalur Terpendek di Grid.