Belajar Data Structure - BFS & DFS
BFS dan DFS adalah dua metode traversal graph fundamental. Di episode ini kalian memahami BFS level-order dengan queue untuk shortest path unweighted, DFS depth-first dengan stack/recursion untuk cycle detection, serta mempraktikkan BFS shortest path grid dan DFS deteksi cycle.
#Pendahuluan
Setelah di episode 15 kita memahami representasi graph — adjacency list vs adjacency matrix — pada episode ini kita mempelajari BFS (Breadth-First Search) dan DFS (Depth-First Search), dua metode traversal fundamental yang menjadi fondasi untuk hampir semua algoritma graph lainnya.
BFS dan DFS mengeksplorasi graph dengan strategi berbeda: BFS menelusuri level demi level (seperti riak air yang menyebar), sementara DFS menelusuri sedalam mungkin sebelum mundur (seperti maze solving). Memahami kapan menggunakan mana adalah keterampilan yang akan kalian pakai berulang kali.
#BFS (Breadth-First Search)
#Konsep
BFS mengeksplorasi semua node pada level yang sama sebelum pindah ke level berikutnya. Menggunakan queue untuk menjaga urutan eksplorasi.
#Implementasi
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result#Shortest Path Unweighted
BFS menjamin shortest path pada graph unweighted karena ia mengeksplorasi semua node pada distance d sebelum pindah ke distance d+1.
def bfs_shortest_path(graph, start, end):
queue = deque([(start, [start])])
visited = {start}
while queue:
node, path = queue.popleft()
if node == end:
return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None#Connected Components
BFS bisa digunakan untuk menemukan semua connected components dalam graph — kelompok node yang saling terhubung.
def connected_components(graph):
visited = set()
components = []
for node in graph:
if node not in visited:
component = bfs(graph, node)
components.append(component)
visited.update(component)
return components#DFS (Depth-First Search)
#Konsep
DFS mengeksplorasi sedalam mungkin sepanjang satu jalur sebelum backtracking. Menggunakan stack (atau recursion) untuk menjaga urutan eksplorasi.
#Implementasi Iteratif (Stack)
def dfs_iterative(graph, start):
visited = set()
stack = [start]
result = []
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
result.append(node)
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return result#Implementasi Rekursif
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
result = [node]
for neighbor in graph[node]:
if neighbor not in visited:
result.extend(dfs_recursive(graph, neighbor, visited))
return result#Cycle Detection
DFS bisa mendeteksi cycle dalam graph — cycle terjadi jika DFS menemui node yang sudah dikunjungi tapi bukan parent.
def has_cycle(graph):
WHITE, GRAY, BLACK = 0, 1, 2
color = {node: WHITE for node in graph}
def dfs(node):
color[node] = GRAY
for neighbor in graph[node]:
if color[neighbor] == GRAY:
return True
if color[neighbor] == WHITE and dfs(neighbor):
return True
color[node] = BLACK
return False
return any(dfs(node) for node in graph if color[node] == WHITE)#Pathfinding
DFS bisa menemukan path antara dua node (bukan shortest, tetapi valid path).
#Praktik: BFS Shortest Path Grid
from collections import deque
def bfs_maze(maze, start, end):
rows, cols = len(maze), len(maze[0])
queue = deque([(start[0], start[1], 0)])
visited = {start}
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while queue:
r, c, dist = queue.popleft()
if (r, c) == end:
return dist
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols
and maze[nr][nc] == 0
and (nr, nc) not in visited):
visited.add((nr, nc))
queue.append((nr, nc, dist + 1))
return -1
maze = [
[0, 0, 0, 0],
[0, 1, 1, 0],
[0, 0, 0, 0],
[1, 1, 0, 0]
]
print(bfs_maze(maze, (0, 0), (3, 3)))#DFS Cycle Detection
directed = {
0: [1],
1: [2],
2: [0],
3: [4],
4: []
}
print("Has cycle:", has_cycle(directed))#Perbandingan BFS vs DFS
| Aspek | BFS | DFS |
|---|---|---|
| Struktur data | Queue | Stack / Recursion |
| Eksplorasi | Level-by-level | Depth-first |
| Shortest path (unweighted) | Ya | Tidak |
| Memory | O(w) | O(h) |
| Use case | Shortest path, level order | Cycle detection, topological sort |
w = width (lebar maksimum graph), h = height (kedalaman maksimum).
Tip
BFS menggunakan lebih banyak memory untuk graph lebar, sementara DFS menggunakan lebih banyak memory untuk graph dalam. Untuk graph dengan branching factor besar (misal: pohon decision), DFS lebih hemat memory.
#Penutup
Inti yang harus dibawa pulang:
- BFS: queue-based, level-by-level, shortest path unweighted, O(w) memory.
- DFS: stack/recursion-based, depth-first, cycle detection, O(h) memory.
- BFS untuk: shortest path, connected components, level-order traversal.
- DFS untuk: cycle detection, topological sort, pathfinding.
- Directed graph cycle detection: DFS dengan coloring (white/gray/black).
Di episode 17 selanjutnya kita akan membahas topological sort dan cycle detection — pengurutan node berdasarkan dependency, hanya untuk DAG (Directed Acyclic Graph), serta aplikasinya di build order dan course prerequisite. Pastikan kalian sudah paham BFS dan DFS karena keduanya akan digunakan di episode ini!