Graphs & BFS / DFS

A graph is a set of nodes (vertices) connected by edges. Unlike trees, graphs can have cycles, multiple paths, and disconnected components.

Representations:
• Adjacency List → dict mapping node to list of neighbors. Space O(V+E). Best for sparse graphs
• Adjacency Matrix → 2D array. Space O(V²). Good for dense graphs, O(1) edge lookup

DFS (Depth-First Search): go as deep as possible before backtracking.
→ Uses stack (recursion call stack or explicit)
→ Good for: cycle detection, topological sort, connected components, paths

BFS (Breadth-First Search): explore all neighbors before going deeper.
→ Uses queue
→ Good for: shortest path (unweighted), level-order, minimum steps

Key graph problems:
• Number of islands → DFS/BFS flood fill
• Clone graph → DFS with visited map
• Course schedule → topological sort / cycle detection
• Word ladder → BFS shortest path
• Dijkstra → shortest path in weighted graph

1from collections import deque, defaultdict
2
3# ── DFS (recursive) ───────────────────────────────────────────────
4def dfs(graph: dict, start: int, visited=None) -> list:
5    if visited is None: visited = set()
6    visited.add(start)
7    result = [start]
8    for neighbor in graph.get(start, []):
9        if neighbor not in visited:
10            result.extend(dfs(graph, neighbor, visited))
11    return result
12
13# ── BFS (iterative) ───────────────────────────────────────────────
14def bfs(graph: dict, start: int) -> list:
15    visited = {start}
16    queue   = deque([start])
17    result  = []
18    while queue:
19        node = queue.popleft()
20        result.append(node)
21        for neighbor in graph.get(node, []):
22            if neighbor not in visited:
23                visited.add(neighbor)
24                queue.append(neighbor)
25    return result
26
27# ── Number of Islands (grid DFS) ──────────────────────────────────
28def num_islands(grid: list[list[str]]) -> int:
29    if not grid: return 0
30    rows, cols = len(grid), len(grid[0])
31    count = 0
32
33    def dfs(r, c):
34        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
35            return
36        grid[r][c] = '0'    # mark visited by sinking the island
37        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
38
39    for r in range(rows):
40        for c in range(cols):
41            if grid[r][c] == '1':
42                dfs(r, c)
43                count += 1
44    return count
45
46# ── Shortest Path BFS (unweighted) ────────────────────────────────
47def shortest_path(graph: dict, src: int, dst: int) -> int:
48    if src == dst: return 0
49    visited = {src}
50    queue   = deque([(src, 0)])
51    while queue:
52        node, dist = queue.popleft()
53        for neighbor in graph.get(node, []):
54            if neighbor == dst: return dist + 1
55            if neighbor not in visited:
56                visited.add(neighbor)
57                queue.append((neighbor, dist + 1))
58    return -1   # not reachable
59
60# ── Topological Sort (course schedule) ────────────────────────────
61def can_finish(n: int, prerequisites: list[list[int]]) -> bool:
62    graph   = defaultdict(list)
63    in_deg  = [0] * n
64    for a, b in prerequisites:
65        graph[b].append(a)
66        in_deg[a] += 1
67    queue = deque([i for i in range(n) if in_deg[i] == 0])
68    count = 0
69    while queue:
70        node = queue.popleft()
71        count += 1
72        for nei in graph[node]:
73            in_deg[nei] -= 1
74            if in_deg[nei] == 0: queue.append(nei)
75    return count == n   # True = no cycle = can finish
76
77g = {0:[1,2], 1:[3], 2:[4], 3:[], 4:[]}
78print(dfs(g, 0))                              # [0, 1, 3, 2, 4]
79print(bfs(g, 0))                              # [0, 1, 2, 3, 4]
80print(shortest_path(g, 0, 4))                 # 2
81print(can_finish(4, [[1,0],[2,1],[3,2]]))      # True