10 — Graphs

Graph problems on LeetCode span three levels of abstraction:

1. Implicit grid graphs — cells are nodes, 4-directional adjacency is the edge set (flood fill, islands).
2. Explicit adjacency-list graphs — nodes and edges given directly (clone graph, course schedule).
3. Weighted / directed graphs — edges carry costs or directions (shortest paths, topological sort).

The easy tier lives almost entirely in category 1. Mastering the grid traversal template here transfers directly to 80% of the medium problems.

---

Grid Traversal — the Core Template

4-directional neighbors

DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))

def neighbors(r: int, c: int, rows: int, cols: int):
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            yield nr, nc

DFS — recursive

def dfs(grid, r, c, visited):
    if (r, c) in visited:
        return
    visited.add((r, c))
    for nr, nc in neighbors(r, c, len(grid), len(grid[0])):
        if grid[nr][nc] == 1:          # whatever condition
            dfs(grid, nr, nc, visited)

In-place marking (avoids a separate visited set — mutates the grid):

def dfs(grid, r, c):
    grid[r][c] = 0                     # mark visited by zeroing / painting
    for nr, nc in neighbors(r, c, len(grid), len(grid[0])):
        if grid[nr][nc] == 1:
            dfs(grid, nr, nc)

Use in-place marking when the problem allows mutation and you want O(1) extra space. Use a visited set when you must preserve the original grid.

BFS — collections.deque

import collections

def bfs(grid, sr, sc):
    rows, cols = len(grid), len(grid[0])
    queue = collections.deque([(sr, sc)])
    grid[sr][sc] = 0                   # mark on enqueue, not on dequeue
    while queue:
        r, c = queue.popleft()
        for nr, nc in neighbors(r, c, rows, cols):
            if grid[nr][nc] == 1:
                grid[nr][nc] = 0
                queue.append((nr, nc))

BFS vs DFS on grids

Concern	DFS (recursive)	BFS (deque)
Shortest path	No	Yes (unweighted)
Stack overflow risk	Yes (deep grids)	No
Code length	Shorter	Slightly longer
Memory	O(depth) stack	O(width) queue

Rule of thumb: use BFS whenever the problem asks for minimum steps / distance; use DFS when you only care about reachability or total size.

---

Multi-source BFS (preview — medium/hard tier)

Some problems seed BFS from multiple starting cells simultaneously (e.g., 994 Rotting Oranges, 286 Walls and Gates, 417 Pacific Atlantic). The pattern is identical to single-source BFS, but you enqueue all source cells before the main loop:

queue = collections.deque()
for r in range(rows):
    for c in range(cols):
        if is_source(grid[r][c]):
            queue.append((r, c))
            grid[r][c] = VISITED
# then the standard BFS loop

---

Union-Find (preview — medium/hard tier)

For problems that ask "how many connected components?" or handle dynamic edge additions (684 Redundant Connection, 305 Number of Islands II), Union-Find (Disjoint Set Union) offers O(α(n)) per operation:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

---

ML Relevance

Graph concept	ML application
Flood fill / connected components	Image segmentation (region growing), semantic labeling
BFS shortest path	Knowledge graph traversal, recommendation system reachability
Multi-source BFS	Distance transforms in convolutional networks
Graph Neural Networks (GNNs)	Node classification, link prediction, molecular property prediction
Union-Find components	Clustering (single-linkage), dataset deduplication
Topological sort (DAG)	Dependency resolution in ML pipelines, DAG-structured computation graphs

---

Solved — Easy

#	Problem	Technique	Time	Space
733	Flood Fill	Grid DFS (recursive) + BFS variant	O(m×n)	O(m×n) stack
463	Island Perimeter	Grid scan / contribution counting	O(m×n)	O(1)

---

Solved — Medium

#	Problem	Technique	Time	Space
130	Surrounded Regions	DFS from border O's; flip remaining	O(m·n)	O(m·n)
133	Clone Graph	DFS + original→clone hash map	O(V+E)	O(V)
207	Course Schedule	Kahn's BFS topological sort (cycle detection)	O(V+E)	O(V+E)
210	Course Schedule II	Kahn's BFS topological sort (ordering)	O(V+E)	O(V+E)
417	Pacific Atlantic Water Flow	Multi-source BFS from both ocean borders	O(m·n)	O(m·n)
547	Number of Provinces	Union-Find; DFS alternative	O(n²·α(n))	O(n)
684	Redundant Connection	Union-Find; first cycle edge	O(n·α(n))	O(n)
994	Rotting Oranges	Multi-source BFS, levels = minutes	O(m·n)	O(m·n)
1466	Reorder Routes	BFS with edge-direction cost encoding	O(n)	O(n)

Remaining Medium (not yet solved)

#	Problem	Key idea
286	Walls and Gates	Multi-source BFS from all gates

---

Then: Hard

#	Problem	Key idea
127	Word Ladder	BFS on implicit word graph, bidirectional BFS optimization
269	Alien Dictionary	Topological sort from character ordering constraints
743	Network Delay Time	Dijkstra's algorithm (single-source shortest path)
787	Cheapest Flights Within K Stops	Bellman-Ford with at-most-K relaxations
305	Number of Islands II	Online Union-Find with dynamic land additions