# Graph Interview Patterns: A Complete Guide (2025)

Source: https://www.techinterview.org/post/3233460806/graph-interview-patterns/
Updated: 2026-04-17 · techinterview.org

Graph problems appear in every serious technical interview. They cover a wide range of difficulty — from simple BFS/DFS traversal to Dijkstra and Union-Find. The good news: most graph interview problems reduce to one of six patterns. Recognizing the pattern is half the solution.

## Graph Representation

Two standard representations:


```
# Adjacency list (most common for sparse graphs)
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # undirected

# Adjacency matrix (dense graphs or when O(1) edge lookup needed)
n = 5
adj = [[0]*n for _ in range(n)]
for u, v in edges:
    adj[u][v] = adj[v][u] = 1
```


## Pattern 1: Connected Components (DFS / BFS)

Count connected components or check if all nodes are reachable. Classic: Number of Islands, Number of Provinces.


```
def numComponents(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v); graph[v].append(u)

    visited = set()
    count = 0

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

    for i in range(n):
        if i not in visited:
            dfs(i)
            count += 1
    return count
```

For grids: treat each cell as a node, neighbors are the 4 (or 8) adjacent cells. Mark visited by modifying the grid in-place to avoid an extra set.

## Pattern 2: Shortest Path in Unweighted Graph (BFS)

BFS guarantees the shortest path in unweighted graphs — the first time a node is reached is via the shortest path. Use for: minimum number of steps, minimum word transformations (Word Ladder), minimum moves on a grid.


```
from collections import deque

def bfs_shortest_path(graph, start, end):
    queue = deque([(start, 0)])  # (node, distance)
    visited = {start}
    while queue:
        node, dist = queue.popleft()
        if node == end:
            return dist
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1  # no path
```

Multi-source BFS: add all sources to the queue initially. The distance to each cell is from the nearest source. Used for: 01 Matrix (distance to nearest 0), Rotting Oranges (distance from any rotten orange).

## Pattern 3: Shortest Path in Weighted Graph (Dijkstra)

Dijkstra finds shortest paths from a source when edge weights are non-negative. Time O((V + E) log V) with a min-heap.


```
import heapq

def dijkstra(graph, start):
    # graph[u] = [(weight, v), ...]
    dist = {node: float("inf") for node in graph}
    dist[start] = 0
    heap = [(0, start)]  # (distance, node)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # stale entry, skip
        for weight, v in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(heap, (dist[v], v))
    return dist
```

LeetCode applications: Network Delay Time (743), Cheapest Flights Within K Stops (787, modified Dijkstra), Path With Minimum Effort (1631).

## Pattern 4: Topological Sort (Kahn or DFS)

Order nodes such that all edges point forward. Use for: task scheduling, course prerequisites, build dependency resolution.


```
from collections import deque

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

    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == n else []  # empty list = cycle
```


## Pattern 5: Union-Find (Disjoint Set Union)

Dynamically group elements and query if two elements are in the same group. O(alpha(n)) ≈ O(1) amortized with path compression and union by rank.


```
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = 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
        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
        self.components -= 1
        return True
```

Use for: detecting cycles in undirected graphs, minimum spanning tree (Kruskal), redundant connection, accounts merge.

## Pattern 6: Cycle Detection

Undirected: Union-Find or DFS (track parent to avoid revisiting). Directed: DFS with three-color marking (white=unvisited, gray=in-stack, black=done). If you encounter a gray node, there is a cycle.


```
def hasCycle(n, edges):
    # Directed graph
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def dfs(u):
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:
                return True  # back edge = cycle
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False

    return any(dfs(i) for i in range(n) if color[i] == WHITE)
```


## Grid as Graph

Many graph problems disguise themselves as grid problems. Treat each cell (r, c) as node r*cols+c. Neighbors are the 4 adjacent cells. Apply BFS/DFS/Union-Find as normal. Common patterns: flood fill (Number of Islands), BFS for minimum distance (01 Matrix, Walls and Gates), DFS for reachability (Pacific Atlantic Water Flow, Surrounded Regions).

## Recognition Guide

| Pattern | Signal in Problem |
| --- | --- |
| BFS (unweighted shortest) | "minimum steps," "minimum transformations," level-order |
| Dijkstra | "minimum cost/distance," weighted graph, non-negative weights |
| Bellman-Ford | "negative weights," "detect negative cycle," "at most K edges" |
| Topological sort | "dependency order," "course prerequisites," DAG |
| Union-Find | "connected components," "number of groups," "merge accounts" |
| DFS backtrack | "find all paths," "paths with constraint" |

## Frequently Asked Questions

### When should you use Dijkstra vs BFS vs Bellman-Ford?

BFS finds shortest paths in unweighted graphs (or where all edge weights are equal) in O(V + E) time. It is the first choice for: minimum hops, minimum steps on a grid, Word Ladder. Dijkstra handles weighted graphs with non-negative weights in O((V + E) log V) with a min-heap. Use for: network routing, minimum cost path when weights represent distances or costs. Bellman-Ford handles negative weights and detects negative cycles in O(V * E) time — much slower than Dijkstra. Use when: the graph may have negative edges (currency arbitrage, relaxed shortest path with K stops). In LeetCode, Bellman-Ford appears in problems with a constraint on number of edges (Cheapest Flights Within K Stops) where Dijkstra without modification would not respect the K-hop limit.

### How does Union-Find detect cycles in an undirected graph?

Union-Find detects cycles by tracking connected components. Initialize each node as its own component. Process edges one by one: for each edge (u, v), find the root of u and the root of v. If they share the same root, u and v are already in the same component, meaning this edge creates a cycle — return True. If different roots, union them (merge the two components) and continue. After processing all edges without finding a shared root, return False — no cycle. This approach runs in O(E * alpha(V)) ≈ O(E) time. Compare with DFS cycle detection: DFS also runs O(V + E) but requires explicit recursion and a visited/in-stack state. Union-Find is simpler for undirected graphs. For directed graphs, Union-Find does not apply because directionality matters — use three-color DFS (white/gray/black) instead.

### What is topological sort and which problems require it?

Topological sort orders the nodes of a DAG (Directed Acyclic Graph) such that for every directed edge from u to v, u appears before v in the ordering. It is only possible in acyclic graphs — if a cycle exists, no valid ordering exists and Kahn's algorithm returns fewer nodes than expected. Two implementations: (1) Kahn's BFS algorithm: initialize a queue with all nodes of in-degree 0; repeatedly dequeue a node, add to result, and decrement neighbors' in-degrees; add any neighbor that reaches 0 to the queue. (2) DFS: after finishing all neighbors of a node, push it to a stack; the stack is the topological order in reverse. Problems requiring topological sort: Course Schedule I and II (LeetCode 207, 210), Alien Dictionary (reconstruct character order from sorted words), Task Scheduling (tasks with prerequisites), Build Systems (Maven, Make — build targets before their dependents). Recognition signal: "do X before Y" constraints on a set of tasks or nodes.

- [Databricks Interview Guide](https://techinterview.org/databricks-interview-guide/)

- [Airbnb Interview Guide](https://techinterview.org/airbnb-interview-guide/)

- [Snap Interview Guide](https://techinterview.org/snap-interview-guide/)

- [Atlassian Interview Guide](https://techinterview.org/atlassian-interview-guide/)

- [Apple Interview Guide](https://techinterview.org/apple-interview-guide/)

- [Uber Interview Guide](https://techinterview.org/uber-interview-guide/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-interview-guide/)

## Companies That Ask This

- [Meta Interview Guide](https://techinterview.org/meta-interview-guide/)

Asked at: [Coinbase Interview Guide](https://techinterview.org/coinbase-interview/)