Struktur Bercabang · Pelajaran 10 dari 10
Penelusuran graf: BFS dan DFS
11 menit baca · BelajarCode
Banyak masalah graf dimulai dengan menelusuri semua simpul yang bisa dicapai dari sebuah simpul awal. Ada dua cara utama.
BFS: menelusuri melebar
Breadth-first search (BFS) mengunjungi simpul lapis demi lapis: semua tetangga langsung dulu, lalu tetangga dari tetangga, dan seterusnya. BFS memakai queue. Pada graf tanpa bobot, BFS menemukan jalur terpendek (paling sedikit sisi).
1from collections import deque23graf = {4 "A": ["B", "C"],5 "B": ["A", "D", "E"],6 "C": ["A", "F"],7 "D": ["B"],8 "E": ["B", "F"],9 "F": ["C", "E", "G"],10 "G": ["F"],11}1213def bfs_jalur(graf, awal, tujuan):14 induk = {awal: None}15 antrean = deque([awal])16 while antrean:17 u = antrean.popleft()18 if u == tujuan:19 break20 for v in graf[u]:21 if v not in induk:22 induk[v] = u23 antrean.append(v)24 if tujuan not in induk:25 return None26 jalur = []27 while tujuan is not None:28 jalur.append(tujuan)29 tujuan = induk[tujuan]30 return jalur[::-1]3132print("Jalur terpendek A ke G:", bfs_jalur(graf, "A", "G"))33print("Jalur terpendek D ke C:", bfs_jalur(graf, "D", "C"))Jalur terpendek A ke G: ['A', 'C', 'F', 'G'] Jalur terpendek D ke C: ['D', 'B', 'A', 'C']
Dictionary induk mencatat dari simpul mana setiap simpul pertama kali ditemukan, sekaligus berfungsi sebagai tanda sudah dikunjungi. Jalurnya dibangun mundur dari tujuan.
DFS: menelusuri mendalam
Depth-first search (DFS) menelusuri satu cabang sedalam mungkin sebelum mundur dan mencoba cabang lain. DFS bisa ditulis dengan rekursi (yang memakai call stack) atau dengan stack biasa.
1graf = {2 "A": ["B", "C"],3 "B": ["A", "D", "E"],4 "C": ["A", "F"],5 "D": ["B"],6 "E": ["B", "F"],7 "F": ["C", "E", "G"],8 "G": ["F"],9}1011def dfs(graf, u, dikunjungi, urutan):12 dikunjungi.add(u)13 urutan.append(u)14 for v in graf[u]:15 if v not in dikunjungi:16 dfs(graf, v, dikunjungi, urutan)17 return urutan1819print("Urutan DFS dari A:", dfs(graf, "A", set(), []))Urutan DFS dari A: ['A', 'B', 'D', 'E', 'F', 'C', 'G']
| BFS | DFS | |
|---|---|---|
| Struktur bantu | Queue | Stack atau rekursi |
| Urutan kunjungan | Lapis demi lapis | Sedalam mungkin, lalu mundur |
| Jalur terpendek tanpa bobot | Ya | Tidak dijamin |
| Kompleksitas | O(V + E) | O(V + E) |
| Contoh pemakaian | Jarak minimum, tingkat pertemanan | Mendeteksi siklus, komponen terhubung, topological sort |
Graf berbentuk grid
Peta labirin adalah graf tersembunyi: setiap sel adalah simpul, dan sel yang bersebelahan terhubung. BFS menemukan jumlah langkah minimum dari S ke T.
1from collections import deque23peta = [4 "S.#.....",5 ".##.###.",6 "....#...",7 "##.##.#.",8 "......#T",9]1011def langkah_minimum(peta):12 baris, kolom = len(peta), len(peta[0])13 awal = next((r, c) for r in range(baris) for c in range(kolom) if peta[r][c] == "S")14 jarak = {awal: 0}15 antrean = deque([awal])16 while antrean:17 r, c = antrean.popleft()18 if peta[r][c] == "T":19 return jarak[(r, c)]20 for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:21 nr, nc = r + dr, c + dc22 if 0 <= nr < baris and 0 <= nc < kolom and peta[nr][nc] != "#" and (nr, nc) not in jarak:23 jarak[(nr, nc)] = jarak[(r, c)] + 124 antrean.append((nr, nc))25 return -12627print("Langkah minimum:", langkah_minimum(peta))Langkah minimum: 15
Cek pemahaman
Kenapa BFS menemukan jalur dengan sisi paling sedikit pada graf tanpa bobot?
Latihan
Menghitung pulau
Pada peta berikut, # adalah daratan dan . adalah laut. Daratan yang bersebelahan (atas, bawah, kiri, kanan) membentuk satu pulau. Hitung banyaknya pulau dengan DFS atau BFS.
##...# #...## ..#... ...... ##..##
Pembahasan
1peta = [2 "##...#",3 "#...##",4 "..#...",5 "......",6 "##..##",7]89def hitung_pulau(peta):10 baris, kolom = len(peta), len(peta[0])11 dikunjungi = set()1213 def jelajah(r, c):14 stack = [(r, c)]15 dikunjungi.add((r, c))16 while stack:17 r, c = stack.pop()18 for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:19 nr, nc = r + dr, c + dc20 if (0 <= nr < baris and 0 <= nc < kolom and peta[nr][nc] == "#"21 and (nr, nc) not in dikunjungi):22 dikunjungi.add((nr, nc))23 stack.append((nr, nc))2425 pulau = 026 for r in range(baris):27 for c in range(kolom):28 if peta[r][c] == "#" and (r, c) not in dikunjungi:29 pulau += 130 jelajah(r, c)31 return pulau3233print("Banyak pulau:", hitung_pulau(peta))Banyak pulau: 5
Setiap kali menemukan daratan yang belum dikunjungi, berarti ada pulau baru. DFS kemudian menandai seluruh daratan pulau itu supaya tidak dihitung lagi. Teknik ini disebut mencari komponen terhubung.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.