# Graph Algorithm Patterns for Coding Interviews

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

## Why Graph Algorithms Matter in Interviews

Graph problems appear constantly in technical interviews because they model real systems: social networks (friend-of-friend), maps and routing (shortest path), dependency resolution (topological sort), and network connectivity (union-find). The key is recognizing which algorithm to apply: BFS for shortest paths in unweighted graphs, DFS for cycle detection and connected components, Dijkstra for weighted shortest paths, and topological sort for dependency ordering.

## Pattern 1: BFS for Shortest Path

Use BFS when edge weights are uniform (or 1). BFS explores nodes level by level — the first time you reach the target, it's via the shortest path.


```
from collections import deque

def bfs_shortest_path(graph, start, end):
    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        node, path = queue.popleft()
        if node == end:
            return path

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None  # no path exists

# Applications: word ladder, maze solving, shortest path in unweighted graph
```


## Pattern 2: DFS for Cycle Detection

Use DFS with three states: WHITE (unvisited), GRAY (in current DFS path), BLACK (fully processed). A back edge to GRAY = cycle.


```
def has_cycle_directed(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

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

    return any(dfs(node) for node in graph if color[node] == WHITE)
```


## Pattern 3: Topological Sort (Kahn's Algorithm)

For DAGs (directed acyclic graphs): order nodes so every edge goes from earlier to later. Used for: build systems, course prerequisites, task scheduling.


```
from collections import deque, defaultdict

def topological_sort(n, edges):
    # edges = [(0,1), (0,2), (1,3), (2,3)] (prerequisite -> course)
    in_degree = [0] * n
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 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 adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

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


## Pattern 4: Dijkstra's Algorithm

Shortest path in weighted graphs (non-negative weights). Use a min-heap to always expand the cheapest unvisited node.


```
import heapq

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

    while heap:
        cost, node = heapq.heappop(heap)
        if cost > dist[node]:
            continue  # stale entry
        for weight, neighbor in graph[node]:
            new_cost = cost + weight
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                heapq.heappush(heap, (new_cost, neighbor))

    return dist
```

Time complexity: O((V + E) log V). Cannot handle negative edge weights — use Bellman-Ford instead.

## Pattern 5: Union-Find for Connected Components

Efficiently track connected components with path compression and union by rank. Each element points to a root; two elements are connected if they share a root.


```
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

# Applications: number of islands II, accounts merge, redundant connections
```


## Algorithm Selection Guide

| Problem | Algorithm | Complexity |
| --- | --- | --- |
| Shortest path, unweighted | BFS | O(V+E) |
| Shortest path, weighted | Dijkstra | O((V+E) log V) |
| Shortest path, negative weights | Bellman-Ford | O(VE) |
| All-pairs shortest path | Floyd-Warshall | O(V³) |
| Cycle detection (directed) | DFS (3-color) | O(V+E) |
| Topological ordering | Kahn's BFS | O(V+E) |
| Connected components | Union-Find | O(α(N)) per op |
| Minimum spanning tree | Kruskal/Prim | O(E log E) |

## Key Interview Tips

  - BFS vs DFS: BFS for shortest path, DFS for exhaustive search and cycle detection

  - Always check for disconnected graphs — iterate over all nodes to start DFS/BFS

  - Topological sort can also detect cycles: if output length < n, a cycle exists

  - Union-Find is O(α(n)) ≈ O(1) amortized — prefer it over BFS/DFS for repeated connectivity queries

  - Grid problems are graph problems: cells are nodes, adjacent cells are edges

Graph algorithm patterns are commonly tested at [Google coding interview questions](https://www.techinterview.org/post/3233460274/netflix-interview-guide-2026-streaming-architecture-recommendation-systems-and-engineering-excellence/).

BFS, DFS, Dijkstra, and topological sort patterns appear in [Meta coding interview preparation](https://www.techinterview.org/post/3233460272/meta-interview-guide-2026-facebook-instagram-whatsapp-engineering/).

Graph traversal and shortest path problems are tested in [Amazon coding interview guide](https://www.techinterview.org/post/3233460275/scale-ai-interview-guide-2026-data-infrastructure-rlhf-pipelines-and-ml-engineering/).