Top 12 Graph Interview Problems: Every Pattern You'll See

Graph problems have a reputation for being hard. They're not. They just come in disguise.

A grid of land and water is a graph. A list of course prerequisites is a graph. A word game where you swap one letter at a time is a graph. You will sit in an interview, stare at what looks like a matrix problem, and your brain will completely blank because it doesn't file "matrix" and "graph" in the same mental folder. The interview skill isn't DFS fluency. It's recognizing the graph before you write a single line of code.

These 12 graph interview problems cover every pattern the interview circuit actually tests, ordered by difficulty, with the core insight each one teaches. Solve these in order and the rest of the graph category becomes pattern-matching, not problem-solving.

The Five Primitives Behind Every Graph Problem

Every graph problem in this guide uses some combination of five tools.

DFS for connectivity, cycle detection, path existence
BFS for shortest paths in unweighted graphs, level-by-level propagation
Topological sort for dependency ordering and directed cycle detection
Union-Find for dynamic connectivity and undirected cycle detection
Dijkstra for weighted shortest paths

That's the whole toolkit. Five tools, twelve problems, zero mysteries. The 12 problems below teach you when and how to reach for each one.

Problem 1: Number of Islands (LeetCode 200)

Pattern: DFS flood fill | Difficulty: Medium

What it teaches: A 2D grid is a graph. Each cell is a node. Each adjacent cell is an edge. This sounds obvious in retrospect and will not feel obvious at all in the interview. This is the foundational pattern behind every matrix-based graph problem you'll see.

def numIslands(grid: list[list[str]]) -> int:
    def dfs(r, c):
        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
            return
        if grid[r][c] != '1':
            return
        grid[r][c] = '#'
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            dfs(r + dr, c + dc)

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

The non-obvious part: You don't need a separate visited set. Mutating the grid in-place (marking '#') is both correct and saves space. Interviewers love this. If you can't mutate the input, use a set of (row, col) tuples, which is the boring-but-safe backup.

Problem 2: Clone Graph (LeetCode 133)

Pattern: DFS with identity tracking | Difficulty: Medium

What it teaches: Graphs can have cycles, so naive DFS loops forever. Fun to discover this at 2am the night before your interview. Less fun to discover it in the interview itself. This problem forces you to track node identity, not just visited status. The visited map also doubles as the cloned node registry, which is genuinely elegant.

def cloneGraph(node):
    cloned = {}

    def dfs(n):
        if n in cloned:
            return cloned[n]
        copy = Node(n.val)
        cloned[n] = copy
        for neighbor in n.neighbors:
            copy.neighbors.append(dfs(neighbor))
        return copy

    return dfs(node) if node else None

Store the cloned node in the map before recursing into neighbors. Doing it after causes infinite loops on cyclic graphs. This ordering bug is what interviewers watch for, so narrate it explicitly: "I'm storing the clone before recursing to break cycles."

Problem 3: Rotting Oranges (LeetCode 994)

Pattern: Multi-source BFS | Difficulty: Medium

What it teaches: When multiple sources spread simultaneously, DFS models the propagation wrong. DFS goes deep on one source before touching others, which gives you incorrect timing. Think of it like a fire starting in twelve places at once. You don't extinguish one building, then move to the next. The key insight: initialize the queue with all rotting oranges at once, not one at a time.

from collections import deque

def orangesRotting(grid):
    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, 0))
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    while queue:
        r, c, t = queue.popleft()
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            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
                minutes = t + 1
                queue.append((nr, nc, t + 1))

    return minutes if fresh == 0 else -1

This multi-source initialization pattern reappears in Problems 6 and 11. Learn it here, not by re-deriving it from scratch twice more.

Problem 4: Course Schedule (LeetCode 207)

Pattern: Cycle detection in a directed graph | Difficulty: Medium

What it teaches: Cycles in directed graphs break topological ordering. If you can complete all courses, no cycle exists. This maps cleanly onto any problem asking "is this dependency graph valid?" which turns out to be a lot of problems.

The DFS approach uses three states: unvisited (0), in-progress (1), done (2). Finding a node in state 1 during DFS means you've found a back edge, which means you've found a cycle. One or two edges is a coincidence. Three states is a system.

def canFinish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        graph[b].append(a)

    state = [0] * numCourses

    def dfs(node):
        if state[node] == 1:
            return False
        if state[node] == 2:
            return True
        state[node] = 1
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        state[node] = 2
        return True

    return all(dfs(i) for i in range(numCourses))

Problem 5: Course Schedule II (LeetCode 210)

Pattern: Topological sort | Difficulty: Medium

What it teaches: Same graph as Problem 4, but now you need the actual ordering, not just a yes/no answer. Kahn's algorithm (BFS with in-degree tracking) gives you the order directly and is often cleaner to explain under pressure. Explaining three-color DFS while nervous is an acquired skill. Starting from "I track how many unsatisfied prerequisites each course has" is much easier.

from collections import deque

def findOrder(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        indegree[a] += 1

    queue = deque(i for i in range(numCourses) 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) == numCourses else []

The non-obvious part: If len(order) != numCourses, a cycle exists. You get cycle detection for free from the count check. For a deeper dive, see the topological sort guide.

Problem 6: Pacific Atlantic Water Flow (LeetCode 417)

Pattern: Reverse multi-source DFS | Difficulty: Medium

What it teaches: Sometimes thinking forward is the wrong direction. Simulating water flowing downhill toward both oceans from every cell is a combinatorial mess. Flip it. Ask which cells each ocean can "reach" by flowing uphill. Run two DFS traversals from opposite borders, then intersect the results.

Pacific DFS starts from the top and left borders. Atlantic DFS starts from the bottom and right. Any cell in both sets can reach both oceans. This reversal pattern shows up whenever you need to find all cells reachable from a given boundary. Recognize it as a pattern, not a trick you had to be clever enough to invent.

Problem 7: Redundant Connection (LeetCode 684)

Pattern: Union-Find cycle detection | Difficulty: Medium

What it teaches: Adding an edge between two nodes that already share a component creates a cycle. Union-Find detects this in near-O(1) per operation with path compression. This is the tool you reach for when the graph is undirected and you care about which edges are "extra."

def findRedundantConnection(edges):
    parent = list(range(len(edges) + 1))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return False
        parent[px] = py
        return True

    for u, v in edges:
        if not union(u, v):
            return [u, v]

The non-obvious part: Process edges in order and return the first edge that fails to union. That's your redundant edge. If you're unsure whether a problem wants Union-Find or BFS, the Union-Find pattern guide has the decision criteria.

Problem 8: Word Ladder (LeetCode 127)

Pattern: BFS on an implicit graph | Difficulty: Hard

What it teaches: Some graphs are never handed to you. You construct them on the fly. Each word is a node. Two words share an edge if they differ by exactly one letter. BFS finds the shortest transformation sequence because each BFS level represents exactly one more character swap. The graph exists conceptually even though you never build an adjacency list.

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    wordSet = set(wordList)
    if endWord not in wordSet:
        return 0

    queue = deque([(beginWord, 1)])
    visited = {beginWord}

    while queue:
        word, length = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word == endWord:
                    return length + 1
                if next_word in wordSet and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, length + 1))
    return 0

The performance trap: comparing against the full word list is O(word_length × list_size) per node, which will time out. Generating neighbors by character substitution is O(26 × word_length) per node, which is fine. Use a set for O(1) word lookup. This is one of those problems where the naive implementation works correctly and fails spectacularly on large inputs.

Problem 9: Network Delay Time (LeetCode 743)

Pattern: Dijkstra's algorithm | Difficulty: Medium

What it teaches: When edges have weights and you need shortest paths, BFS breaks. Dijkstra's uses a min-heap to always expand the cheapest unvisited node first. The time for the signal to reach all nodes is the maximum of all shortest-path distances from the source. Simple framing once you see it. Takes a second to see it.

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((w, v))

    dist = {k: 0}
    heap = [(0, k)]

    while heap:
        d, node = heapq.heappop(heap)
        if d > dist.get(node, float('inf')):
            continue
        for weight, neighbor in graph[node]:
            new_dist = d + weight
            if new_dist < dist.get(neighbor, float('inf')):
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))

    return max(dist.values()) if len(dist) == n else -1

The if d > dist[node]: continue line is lazy deletion. Stale heap entries stay in the heap until they pop, but you skip them immediately. It keeps the code simple without needing a decrease-key operation. See the full Dijkstra walkthrough for the correctness proof.

Problem 10: Cheapest Flights Within K Stops (LeetCode 787)

Pattern: Constrained shortest path (Bellman-Ford) | Difficulty: Medium

What it teaches: Dijkstra doesn't handle hop constraints directly. Bellman-Ford's outer loop naturally limits the number of edge relaxations. Running K+1 iterations gives you the shortest path using at most K+1 edges, which is K intermediate stops. Most people reach for Dijkstra here and spend ten minutes wondering why it's not working.

def findCheapestPrice(n, flights, src, dst, k):
    prices = [float('inf')] * n
    prices[src] = 0

    for _ in range(k + 1):
        temp = prices.copy()
        for u, v, w in flights:
            if prices[u] != float('inf') and prices[u] + w < temp[v]:
                temp[v] = prices[u] + w
        prices = temp

    return prices[dst] if prices[dst] != float('inf') else -1

The copy is mandatory. Without it, a single iteration can chain multiple edge relaxations, effectively counting more than one hop. This is the most common bug on this problem and it is invisible in small test cases.

Problem 11: Minimum Cost to Connect All Points (LeetCode 1584)

Pattern: Minimum spanning tree (Prim's) | Difficulty: Medium

What it teaches: When you need to connect all nodes with minimum total edge weight, you want an MST. Here the graph is implicit: every pair of points has an edge weighted by Manhattan distance. That's O(n²) potential edges. You do not want to materialize them all.

Prim's with a min-heap sidesteps this. You never need to build the full edge list. Generate neighbor costs on the fly from the current MST boundary. Kruskal's requires sorting all O(n²) edges upfront, which is slower in practice for this problem shape.

Problem 12: Reconstruct Itinerary (LeetCode 332)

Pattern: Eulerian path (Hierholzer's algorithm) | Difficulty: Hard

What it teaches: Use every edge exactly once. That's an Eulerian path. Regular DFS fails because it gets stuck at dead ends before finishing the path, and then you're sitting there confused about why your otherwise-correct DFS produces wrong output. The fix is postorder DFS: add each node to the itinerary only after exhausting all its outgoing edges, then reverse the result.

from collections import defaultdict

def findItinerary(tickets):
    graph = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)

    result = []

    def dfs(node):
        while graph[node]:
            dfs(graph[node].pop())
        result.append(node)

    dfs("JFK")
    return result[::-1]

Sort edges in reverse order before building the graph so pop() gives you the lexicographically smallest next destination. The postorder DFS handles dead ends correctly without explicit backtracking. Dead ends get added first, appear last after reversal. Read that sentence twice before the interview.

How to Practice Graph Interview Problems

Don't solve all 12 in one sitting. That's a great way to feel productive and retain nothing. Solve each problem to real understanding: close the solution, implement from memory an hour later, then explain the core insight out loud. If you can't explain it, you don't know it yet.

The pairings that matter:

207 and 210 are the same graph, two different outputs. Do them back to back.
743 and 787 teach Dijkstra and where it breaks down. Solve 743 until Dijkstra is automatic, then 787.
200 and 994 both live in matrix graphs. Note the multi-source switch between them and understand exactly why BFS is required for 994.
133 and 332 both require careful operation ordering inside DFS. Clone Graph stores the node before recursing to break cycles. Reconstruct Itinerary appends the node after exhausting edges to handle dead ends. Different problems, same discipline of thinking about when exactly you touch the data structure.

Practice saying the graph representation out loud before coding. "This is a directed graph. I need to detect a cycle. I'll use three-color DFS." That narration is what the interviewer is scoring. For structured practice under real interview conditions, SpaceComplexity runs live graph problem sessions with rubric-based feedback on your communication, not just whether your code passed.

For recognizing which pattern to reach for before the problem announces itself, see the DFS pattern guide and BFS pattern guide.

Key Takeaways

Graph recognition is the real skill. Most problems don't label themselves as graphs.
Topological sort has two implementations: DFS postorder and Kahn's BFS. Kahn's detects cycles for free via the node count check.
Union-Find cycle detection: if find(u) == find(v) before union, the edge creates a cycle.
When the graph isn't given explicitly, build it on the fly. Word Ladder and Minimum Cost to Connect All Points both do this.
Eulerian path problems use postorder DFS, not regular DFS. Append after exhausting edges, then reverse.