Graph Algorithm Interview Questions: Patterns and Solutions for 2026

Graph problems represent 25–30% of FAANG coding interviews. Many candidates skip them and pay the price. This guide gives you the pattern library to confidently handle any graph problem you encounter.

Graph Representations

Before algorithms, know how to represent graphs in code:

Adjacency list (most common in interviews):

graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 4],
    3: [1],
    4: [2]
}

Building from edges:

from collections import defaultdict

def build_graph(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # Remove for directed graph
    return graph

Pattern 1: BFS (Shortest Path, Level Order)

BFS explores nodes level by level. Use for:

• Shortest path in unweighted graphs
• Finding minimum steps/moves
• Level-order tree traversal
• Connectivity in unweighted graphs

Template:

from collections import deque

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

Problems: Word Ladder, Shortest Path in Binary Matrix, Rotting Oranges, Minimum Knight Moves, Open the Lock

Pattern 2: DFS (Connectivity, Path Finding, Cycle Detection)

DFS explores as deep as possible before backtracking. Use for:

• Finding connected components
• Path existence (not shortest path)
• Cycle detection
• Topological sort (iterative)
• Generating all paths

Template:

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

Problems: Number of Islands, Clone Graph, Course Schedule, Pacific Atlantic Water Flow, Word Search

Pattern 3: Topological Sort (Dependency Resolution)

For directed acyclic graphs (DAGs). Use when you need ordering where A must come before B.

Kahn's Algorithm (BFS-based):

from collections import deque

def topological_sort(n, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * n
    
    for u, v in prerequisites:
        graph[v].append(u)
        in_degree[u] += 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 = cycle detected

Problems: Course Schedule I & II, Alien Dictionary, Task Scheduler, Build Order

Pattern 4: Dijkstra's (Weighted Shortest Path)

For weighted graphs where edge weights are non-negative. Use for minimum cost path.

import heapq

def dijkstra(graph, start, n):
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]  # (distance, node)
    
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue
        for neighbor, weight in graph[node]:
            if dist[node] + weight < dist[neighbor]:
                dist[neighbor] = dist[node] + weight
                heapq.heappush(heap, (dist[neighbor], neighbor))
    
    return dist

Problems: Network Delay Time, Cheapest Flights Within K Stops, Path With Minimum Effort

Pattern 5: Union-Find (Connected Components)

Union-Find (Disjoint Set Union) efficiently tracks which nodes are in the same connected component.

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

Problems: Number of Connected Components, Redundant Connection, Accounts Merge, Making a Large Island

Pattern 6: Matrix as Graph

Many matrix problems are graph problems in disguise. Key insight: each cell (i, j) is a node, edges connect to 4 (or 8) neighbors.

Direction vectors:

dirs = [(0,1), (0,-1), (1,0), (-1,0)]  # 4-directional

def in_bounds(r, c, rows, cols):
    return 0 <= r < rows and 0 <= c < cols

Problems: Number of Islands, Max Area of Island, Walls and Gates, Surrounded Regions, 01 Matrix

How to Identify the Right Pattern

| Problem asks for... | Pattern | |--------------------|---------| | Shortest path, unweighted | BFS | | Shortest path, weighted | Dijkstra | | Any path exists | DFS | | All paths | DFS + backtracking | | Ordering / dependencies | Topological sort | | Connected components | DFS / BFS / Union-Find | | Dynamic components (online) | Union-Find |

The Graph Problems You Must Know

1. Number of Islands (matrix DFS)
2. Clone Graph (DFS with visited hashmap)
3. Course Schedule II (topological sort)
4. Word Ladder (BFS + word transformation)
5. Network Delay Time (Dijkstra)
6. Cheapest Flights Within K Stops (modified Dijkstra/Bellman-Ford)
7. Pacific Atlantic Water Flow (reverse DFS from both oceans)
8. Number of Connected Components in Undirected Graph (Union-Find)
9. Accounts Merge (Union-Find)
10. Alien Dictionary (topological sort)

Practice graph problems out loud with CareerLift.ai — explaining your graph algorithm choice and walking through the traversal is a skill that matters as much as implementing it.