Graphs

🧠 Spot It

• Input is a network, grid, or dependency structure
• Problem asks for connectivity, shortest path, cycles, ordering
• Keywords: nodes, edges, neighbors, connected components, path

---

Graph Representations

# Adjacency list (most common in interviews)
graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}

# Build from edge list
from collections import defaultdict
def build_graph(edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # remove for directed
    return graph

---

Pattern 1 — DFS (Recursive / Iterative)

def dfs(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

---

Pattern 2 — BFS (Shortest Path in unweighted graph)

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    distance = {start: 0}
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
    return distance

---

Pattern 3 — Topological Sort (Kahn's Algorithm)

What it is, and why it exists

A topological sort is a linear ordering of a graph's nodes such that for every directed edge u → v, u comes before v in the ordering. It only exists for a DAG (Directed Acyclic Graph) — a cycle would demand u before v and v before u simultaneously, which no linear order can satisfy. That's the deep reason topological sort and cycle detection are the same algorithm wearing two hats: Kahn's algorithm below produces a valid order when one exists, and the absence of a full order (fewer nodes processed than exist) is itself the proof a cycle exists.

Why it matters: any "X depends on Y" structure is secretly this problem — course prerequisites, a build system deciding compile order, a package manager resolving install order, a spreadsheet deciding which cells to recalculate first. The signal phrase to listen for is "must be completed before," "depends on," or "prerequisite."

Worked example

Five courses, with prerequisites (prerequisite → course):

0 (Intro)         — no prereq
1 (Data Structures) — needs 0
2 (Algorithms)       — needs 1
3 (Databases)        — needs 0
4 (System Design)    — needs 2 AND 3

Edges: 0→1, 1→2, 0→3, 2→4, 3→4. Indegree (number of prereqs each course still has): [0, 1, 1, 1, 2].

Tracing Kahn's algorithm:

Final order: 0, 1, 3, 2, 4. Check it against every edge: 0 before 1 ✓, 0 before 3 ✓, 1 before 2 ✓, 2 before 4 ✓, 3 before 4 ✓. Any order respecting those pairwise constraints is valid — 0, 3, 1, 2, 4 would also be accepted.

Now the cycle case: add a nonsensical edge 4 → 0 ("System Design is itself a prerequisite of Intro"). Indegree of 0 becomes 1, so the initial queue is empty — nothing ever gets processed, order stays empty, len(order) != n → the function correctly returns [], reporting "impossible to schedule."

from collections import deque, defaultdict

def topo_sort(n, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * n
    for course, pre in prerequisites:
        graph[pre].append(course)
        indegree[course] += 1
    queue = deque([i for i in range(n) if indegree[i] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == n else []  # empty = cycle exists

DFS-based alternative — postorder + reverse. Interviewers sometimes ask for this specifically to check you're not just pattern-matching Kahn's; know both.

def topo_sort_dfs(n, prerequisites):
    graph = defaultdict(list)
    for course, pre in prerequisites:
        graph[pre].append(course)

    visited, on_stack, order = set(), set(), []
    has_cycle = False

    def dfs(node):
        nonlocal has_cycle
        visited.add(node)
        on_stack.add(node)
        for neighbor in graph[node]:
            if neighbor in on_stack:
                has_cycle = True
                return
            if neighbor not in visited:
                dfs(neighbor)
        on_stack.remove(node)
        order.append(node)   # postorder: node appended only after all its dependents are

    for i in range(n):
        if i not in visited:
            dfs(i)
    return [] if has_cycle else order[::-1]   # reverse postorder = topological order

Why reversing postorder works: a node is appended to order only after every node reachable from it has already been appended — so in postorder, dependencies land after their dependents. Reversing puts prerequisites first, exactly the ordering topological sort needs.

---

Pattern 4 — Union Find (Disjoint Set)

What it is, and why it exists

Union Find tracks a collection of elements partitioned into disjoint (non-overlapping) sets — think "which friend group is this person in?" — and answers two questions fast, repeatedly, as new connections arrive:

• find(x) — which set does x belong to? (Returns a representative "root" node for that set.)
• union(x, y) — merge x's set and y's set into one.

The naive way to answer "are x and y connected?" is a fresh BFS/DFS over the whole graph every time — O(V+E) per query. Union Find answers it in near-O(1) (technically O(α(n)), the inverse Ackermann function — so slow-growing it's a constant for any n you'll ever see) by maintaining a forest of parent pointers instead of re-walking edges. Two tricks make this fast:

• Path compression (find) — every node visited during a find gets repointed directly at the root, so the next find on any of them is instant.
• Union by rank (union) — always attach the shorter tree under the taller tree's root, keeping trees flat instead of accidentally building a long chain.

Why it matters: it's the go-to tool whenever a problem is really "group things and answer connectivity questions as groups merge" — undirected cycle detection, counting connected components, Kruskal's MST (Pattern 12), "will adding this edge create a cycle" (Redundant Connection).

Worked example

Six people, 0–5, starting as six separate friend groups. Friendships (edges) arrive one at a time: (0,1), (1,2), (3,4), (5,3).

Now ask: are 2 and 4 connected? find(2) walks 2 → 0 (root). find(4) walks 4 → 3 (root). 0 ≠ 3 → not connected — matches the groups above, no graph re-walk needed.

Cycle detection for free: try adding edge (0, 2). find(0) = 0 and find(2) = 0 — same root already. union returns False immediately, because 0 and 2 are already connected (via 0–1–2), so this new edge would create a cycle. This exact check — union() returning False— is the entire mechanism behind Redundant Connection (LC 684) and behind skipping cycle-forming edges in Kruskal's MST.

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  # already connected (cycle)
        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

---

Pattern 5 — Dijkstra (Weighted Shortest Path)

import heapq

def dijkstra(graph, src):
    dist = {node: float('inf') for node in graph}
    dist[src] = 0
    heap = [(0, src)]  # (cost, node)
    while heap:
        cost, node = heapq.heappop(heap)
        if cost > dist[node]: continue
        for neighbor, weight in graph[node]:
            new_cost = cost + weight
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                heapq.heappush(heap, (new_cost, neighbor))
    return dist

Dijkstra requires non-negative weights. A negative edge can make an already-popped (and assumed-final) node's distance wrong, and Dijkstra never revisits a popped node — it just silently gives the wrong answer, no error. This is exactly why "Cheapest Flights Within K Stops" (LC 787) is not a Dijkstra problem despite looking like one — it needs Bellman-Ford (Pattern 8 below), because the real constraint isn't weight sign, it's a hard cap on path length (≤ K edges), which Dijkstra's greedy "always expand the cheapest known node" has no clean way to enforce. See the decision table below.

Shortest-Path Algorithm — Which One?

---

Pattern 6 — Grid DFS / BFS (4-Directional)

Grid = implicit graph. Cells are nodes, adjacent cells are edges.

# LC 200 — Number of Islands
def numIslands(grid):
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'   # mark visited (in-place)
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

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

# BFS variant — use when you need shortest path / level distances
def bfs_grid(grid, start_r, start_c):
    from collections import deque
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start_r, start_c, 0)])  # (row, col, dist)
    visited = {(start_r, start_c)}
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]

    while queue:
        r, c, dist = queue.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

Key: For DFS, mark visited by mutating grid in-place (restore after if needed) OR use a visited set. BFS = shortest path. DFS = connectivity/count.

---

Pattern 7 — Cycle Detection in Directed Graph

Use DFS with a "currently in stack" set. Back edge = cycle.

def hasCycle(n, edges):
    from collections import defaultdict
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    visited = set()    # fully processed nodes
    in_stack = set()   # current DFS path

    def dfs(node):
        in_stack.add(node)
        for neighbor in graph[node]:
            if neighbor in in_stack:
                return True   # back edge = cycle
            if neighbor not in visited and dfs(neighbor):
                return True
        in_stack.remove(node)
        visited.add(node)
        return False

    return any(dfs(i) for i in range(n) if i not in visited)

Directed vs Undirected: Directed: use in_stack. Undirected: track parent to avoid false cycle from parent edge.

Undirected version — filled in:

def hasCycleUndirected(n, edges):
    from collections import defaultdict
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()

    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor == parent:
                continue                      # skip the edge we just came from
            if neighbor in visited:
                return True                   # reached an already-visited node any other way = cycle
            if dfs(neighbor, node):
                return True
        return False

    return any(dfs(i, -1) for i in range(n) if i not in visited)

Why parent instead of in_stack: in an undirected graph every edge is bidirectional, so u → v and v → u are the same edge stored twice. Without skipping the parent, DFS would immediately "discover" the node it just came from and misreport every single edge as a cycle. Union Find (Pattern 4) is usually the cleaner tool for undirected cycle detection in practice — this DFS version is here because interviewers sometimes ask for it directly to test you understand why directed and undirected cycle detection need different mechanisms.

---

Pattern 8 — Bellman-Ford (Negative Weights, K-Limited Paths, Negative Cycle Detection)

Relax every edge, up to V-1 times — after V-1 rounds, every shortest path (which visits at most V-1 edges in a graph with no negative cycle) is guaranteed found. Slower than Dijkstra (O(V·E) vs O((V+E) log V)), but works with negative edges and can detect negative cycles, which Dijkstra cannot do at all.

def bellman_ford(n, edges, src):   # edges: list of (u, v, weight)
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # one more round: if anything still relaxes, a negative cycle exists
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None   # negative cycle detected
    return dist

K-limited variant — LC 787, Cheapest Flights Within K Stops: cap the relaxation rounds at K+1 instead of V-1, and relax from a snapshot of the previous round (not the array being updated in place) — otherwise a single round could chain multiple hops together and silently violate the stop limit.

def findCheapestPrice(n, flights, src, dst, K):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(K + 1):              # K stops = K+1 edges allowed
        temp = dist[:]                   # snapshot — don't relax off updates made THIS round
        for u, v, w in flights:
            if dist[u] != float('inf') and dist[u] + w < temp[v]:
                temp[v] = dist[u] + w
        dist = temp
    return dist[dst] if dist[dst] != float('inf') else -1

---

Pattern 9 — Floyd-Warshall (All-Pairs Shortest Path)

When you need shortest paths between every pair of nodes, not just from one source — O(V³), so only viable for smaller/dense graphs (roughly V ≤ a few hundred).

def floyd_warshall(n, edges):   # edges: list of (u, v, weight)
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)   # keep the smaller if there's a duplicate edge

    for k in range(n):              # intermediate node
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Core idea: dist[i][j] is repeatedly improved by asking "is going through node k shorter than the current best i → j?" — for every possible intermediate k, in order. By the time k has looped through all n nodes, every path has considered every possible node as a waypoint.

---

Pattern 10 — Bipartite Check (Graph Coloring)

A graph is bipartite if every node can be colored one of 2 colors such that no edge connects two same-colored nodes — equivalently, if it contains no odd-length cycle. BFS or DFS both work; BFS shown here.

from collections import deque

def isBipartite(graph):   # graph[i] = list of i's neighbors
    color = {}
    for start in range(len(graph)):
        if start in color:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in color:
                    color[neighbor] = 1 - color[node]   # opposite color
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False                         # same color on both ends = odd cycle
    return True

Why 1 - color[node] matters more than it looks: this is the entire algorithm — every neighbor must be the opposite color of the current node. The moment a neighbor is found already colored the same as the current node, that's a direct contradiction (an edge between two same-colored nodes), which only happens if there's an odd cycle forcing it.

---

Pattern 11 — Multi-Source BFS

Standard BFS starts from one node. Multi-source BFS seeds the queue with all starting nodes at once, before the first level expands — every source spreads simultaneously, one "layer" per round. The classic tell: "starting from all X at the same time" (all rotten oranges, all fires, all guarded cells).

# LC 994 — Rotting Oranges: minutes until every fresh orange rots, or -1 if impossible
def orangesRotting(grid):
    from collections import deque
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))       # ALL rotten oranges seeded at once — this is the multi-source part
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    while queue and fresh > 0:
        minutes += 1
        for _ in range(len(queue)):        # process one full layer = one minute
            r, c = queue.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))

    return minutes if fresh == 0 else -1

Why this beats running BFS from each source separately: running single-source BFS once per source and taking the min distance is O(sources × (V+E)). Seeding every source into the queue upfront and running BFS once is O(V+E) total — each node still expands from whichever source reaches it first, since BFS naturally processes in increasing-distance order regardless of how many sources started the frontier.

---

Pattern 12 — Minimum Spanning Tree (Kruskal's / Prim's)

MST = the minimum-total-weight set of edges that connects all nodes with no cycles. Two standard approaches:

Kruskal's — sort edges, greedily add if it doesn't create a cycle. Directly reuses the UnionFind class from Pattern 4.

def kruskal(n, edges):   # edges: list of (weight, u, v)
    edges = sorted(edges)
    uf = UnionFind(n)
    total_weight = 0
    mst_edges = []
    for weight, u, v in edges:
        if uf.union(u, v):              # union() returns False if u, v already connected — that's the cycle check
            total_weight += weight
            mst_edges.append((u, v))
    return total_weight, mst_edges

Prim's — grow one tree from a start node, always adding the cheapest edge crossing the frontier. Structurally identical to Dijkstra — a min-heap of (weight, node), expand the cheapest frontier edge instead of the cheapest distance.

import heapq

def prim(n, graph, start=0):   # graph[u] = list of (v, weight)
    visited = {start}
    heap = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(heap)
    total_weight = 0

    while heap and len(visited) < n:
        w, u, v = heapq.heappop(heap)
        if v in visited:
            continue
        visited.add(v)
        total_weight += w
        for nv, nw in graph[v]:
            if nv not in visited:
                heapq.heappush(heap, (nw, v, nv))
    return total_weight

Kruskal's vs Prim's — when each is the right answer: Kruskal's is simpler and usually the first thing to reach for, especially if the edge list is already given (LC 1584, Min Cost to Connect All Points). Prim's is the better fit for dense graphs represented as adjacency lists/matrices where edges aren't naturally enumerable up front — same "grow a frontier with a heap" shape as Dijkstra, worth naming that parallel explicitly if asked.

---

Problems

---

Not covered here (rarely asked outside graph-heavy or staff-level rounds — say if you want any of these added): Tarjan's SCC, articulation points/bridges, A* search, Euler paths/circuits.