9. Graphs

What Interviewers Test Here

• BFS for shortest path (unweighted)
• DFS for connectivity, cycle detection, topological sort
• Union-Find for dynamic connectivity
• Grid problems as implicit graphs

from collections import deque, defaultdict

# --- BFS shortest path ---
def bfs_shortest(graph: dict, start, end) -> int:
    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

# --- DFS: all connected components ---
def num_components(n: int, edges: list[list[int]]) -> int:
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v); graph[v].append(u)
    visited = set()
    def dfs(node):
        visited.add(node)
        for nb in graph[node]:
            if nb not in visited: dfs(nb)
    count = 0
    for node in range(n):
        if node not in visited:
            dfs(node); count += 1
    return count

# --- Union-Find ---
class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank   = [0] * n
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x: int, y: int) -> bool:
        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

---

Conceptual Q&A

Q1: "Given a grid of '0's (water) and '1's (land), count the number of islands."

Walkthrough:

"An island is a group of connected '1's (4-directionally). I need to count connected components of '1's.

Approach: iterate every cell. When I find an unvisited '1', I've found a new island — increment count and run BFS/DFS to mark the entire island as visited (change '1' to '0' or use a visited set).

Why BFS or DFS? Both work for connectivity. DFS is simpler to code (recursive), but can hit Python's recursion limit on large grids. I'll use BFS (iterative) to be safe.

$O(m \times n)$ time and space — each cell visited at most once."

def num_islands(grid: list[list[str]]) -> int:
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def bfs(r: int, c: int) -> None:
        q = deque([(r, c)])
        grid[r][c] = "0"
        while q:
            row, col = q.popleft()
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
                    grid[nr][nc] = "0"
                    q.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                bfs(r, c)
                count += 1
    return count

---

Q2: "Given n courses and prerequisites, determine if you can finish all courses."

Walkthrough:

"This is a cycle detection problem on a directed graph. Each course is a node; a prerequisite [a, b] is a directed edge b → a. I can finish all courses if and only if there is no cycle in this graph (it's a DAG).

I'll use topological sort (Kahn's algorithm):

1. Build the graph and track in-degrees
2. Add all nodes with in-degree 0 to a queue
3. Process nodes: reduce neighbours' in-degrees; add to queue if they reach 0
4. If I processed all $n$ nodes → no cycle (return True). Otherwise a cycle exists."

def can_finish(n: int, prerequisites: list[list[int]]) -> bool:
    graph     = defaultdict(list)
    in_degree = [0] * n
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1

    q = deque(c for c in range(n) if in_degree[c] == 0)
    completed = 0
    while q:
        course = q.popleft()
        completed += 1
        for nxt in graph[course]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                q.append(nxt)

    return completed == n   # True if no cycle

---