Recap — Graph Representation and Traversal

# Graph Representation and Traversal Graphs appear in 15-20% of interview problems. Most "grid", "maze", "network", "dependency" problems are graphs in disguise. ## Three representations ### 1. Adjacency list (most common) ```python graph = { 0: [1, 2], 1: [0, 3], 2: [0, 3, 4], 3: [1, 2, 4], 4: [2, 3], } ``` Or `defaultdict(list)`. Use when graph is sparse (most graphs). Space: O(V + E). Iterating neighbors of node u: O(degree(u)). ### 2. Adjacency matrix ```python graph = [ [0, 1, 1, 0, 0], [1, 0, 0, 1, 0], [1, 0, 0, 1, 1], [0, 1, 1, 0, 1], [0, 0, 1, 1, 0], ] ``` Space: O(V²). Use only when graph is dense or you need O(1) edge-check. ### 3. Edge list ```python edges = [(0,1), (0,2), (1,3), (2,3), (2,4), (3,4)] ``` Just list of edges. Used for input format; usually convert to adjacency list for processing. ## BFS (Breadth-First Search) Explores level by level. Uses a queue. ```python from collections import deque def bfs(graph, start): visited = {start} q = deque([start]) while q: node = q.popleft() for nb in graph[node]: if nb not in visited: visited.add(nb) q.append(nb) return visited ``` ### BFS gives shortest path in UNWEIGHTED graphs ```python def shortest_path_length(graph, start, end): if start == end: return 0 visited = {start} q = deque([(start, 0)]) while q: node, dist = q.popleft() for nb in graph[node]: if nb == end: return dist + 1 if nb not in visited: visited.add(nb) q.append((nb, dist + 1)) return -1 ``` Or track distance map. BFS visits nodes in order of distance from start. ## DFS (Depth-First Search) Explores as deep as possible before backtracking. Recursion or stack. ```python def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) for nb in graph[start]: if nb not in visited: dfs(graph, nb, visited) return visited ``` ### DFS for connectivity, cycles, paths ```python def count_components(graph, n): visited = set() count = 0 for node in range(n): if node not in visited: dfs(graph, node, visited) count += 1 return count ``` ## BFS vs DFS — when to use which | Need | Use | |---|---| | Shortest path (unweighted) | BFS | | Connectivity / components | DFS or BFS (either works) | | Cycle detection | DFS with recursion stack | | Topological sort | DFS (post-order) | | Tree level / "all at depth K" | BFS | | Maze / path exists | DFS | | Closest target | BFS | In doubt: try both, pick the cleaner code. ## Grid problems as graphs Many problems give you a 2D grid and ask "find islands" or "shortest path through maze". Treat each cell as a graph node; neighbors are 4 (or 8) adjacent cells. ```python DIRECTIONS = [(-1,0), (1,0), (0,-1), (0,1)] def count_islands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) visited = [[False] * cols for _ in range(rows)] count = 0 def dfs(r, c): if r = rows or c = cols: return if visited[r][c] or grid[r][c] != '1': return visited[r][c] = True for dr, dc in DIRECTIONS: dfs(r + dr, c + dc) for r in range(rows): for c in range(cols): if grid[r][c] == '1' and not visited[r][c]: dfs(r, c) count += 1 return count ``` The `DIRECTIONS` array and `for dr, dc in DIRECTIONS` pattern is the workhorse for grid problems. ## Visited tracking Always track visited; otherwise you revisit and loop forever in cyclic graphs. - Hashset of nodes: most flexible. - 2D list of bools: faster for grid problems. - Modifying input: mark visited cells with a sentinel (e.g., '#'). Saves space but mutates input. ## Common graph problems - **Number of islands** → DFS/BFS on grid - **Course schedule (cycle detection)** → DFS with recursion stack - **Word ladder (shortest transformation)** → BFS - **Clone a graph** → BFS or DFS with hashmap - **Pacific Atlantic water flow** → reverse BFS from edges - **Rotting oranges** → multi-source BFS ## Common graph mistakes 1. **No visited tracking.** Infinite loop on cycles. 2. **Using DFS for shortest path in unweighted graph.** Doesn't give shortest in general (BFS does). 3. **Mixing recursive DFS with iterative BFS.** Pick a style. 4. **For directed graphs, treating edges as undirected.** Edge `(u, v)` is one-way; check the problem. 5. **For grid problems, going out of bounds.** Always check `0 <= r < rows`. ## Takeaway Graph = nodes + edges. Adjacency list for sparse (most cases). BFS for shortest unweighted path; DFS for connectivity, cycles, post-order. Grid problems = graph problems with implicit edges (4 or 8 directions). Always track visited. Recognize: "shortest" → BFS; "all reachable" → DFS; "cycle" → DFS with