Top 15 Graph Problems to Master for Coding Interviews

Graph problems trip people up not because the algorithms are exotic, but because of one step most candidates skip: modeling the problem as a graph before writing any code. Once you see the nodes and edges, the pattern usually becomes obvious. Until then, you're guessing and sweating and writing BFS on a grid that you didn't realize was a graph.

This list covers fifteen problems, ordered easy to hard, grouped by the pattern they actually teach. Work through each group until you can write the solution from scratch without hints. Then move on. Don't skip groups.

Graph Interview Problems: The Full List

#	Problem	LC	Pattern	Difficulty
1	Number of Islands	200	Grid BFS/DFS	Medium
2	Rotting Oranges	994	Multi-source BFS	Medium
3	Pacific Atlantic Water Flow	417	Reverse BFS	Medium
4	Clone Graph	133	Graph representation	Medium
5	Number of Provinces	547	Union-Find intro	Medium
6	Redundant Connection	684	Union-Find cycle detect	Medium
7	Course Schedule	207	Directed cycle detection	Medium
8	Course Schedule II	210	Kahn's topological sort	Medium
9	All Paths From Source to Target	797	DFS path tracking	Medium
10	Alien Dictionary	269	Abstract graph + topo sort	Hard
11	Word Ladder	127	State-space BFS	Hard
12	Network Delay Time	743	Dijkstra's	Medium
13	Cheapest Flights Within K Stops	787	Bellman-Ford with constraint	Medium
14	Min Cost to Connect All Points	1584	Minimum spanning tree	Medium
15	Critical Connections in a Network	1192	Bridges (Tarjan's)	Hard

Pattern 1: Grid BFS/DFS

A Grid Is a Graph. Yes, Really.

A grid is a graph. Each cell is a node. Adjacent cells are edges. Once that clicks, several problems collapse into one idea. Until that clicks, you'll keep reinventing BFS from scratch with extra loops and a confused expression.

1. Number of Islands (LC 200)

Start a DFS or BFS from every unvisited land cell, marking everything reachable as visited. Count how many times you trigger a new search.

The lesson here isn't the traversal. It's the outer loop. Graphs can be disconnected. A single BFS from one node won't reach everything. Every "count connected components" problem needs an outer loop that walks all unvisited nodes and starts a fresh search. Candidates who skip this loop fail on inputs with multiple disconnected regions, which is exactly the case the interviewer will test.

Time: O(mn). Space: O(mn) call stack worst case (grid is one giant island, you deserve it).

2. Rotting Oranges (LC 994)

Multi-source BFS. Seed the queue with every rotten orange at time zero. Run BFS normally. The minute counter goes up each time you process a full level.

Multi-source BFS is identical to single-source BFS. You just initialize the queue differently. Seed multiple nodes instead of one, and the algorithm handles the rest. You'll reuse this exact setup in Pacific Atlantic Water Flow, Walls and Gates, and 01 Matrix. One pattern, three free problems.

3. Pacific Atlantic Water Flow (LC 417)

The naive approach checks every inland cell and simulates water flowing outward. That's O(mn(m+n)) and will get you a polite smile and a rejection email.

The insight reverses direction: BFS backward from each ocean's boundary to find which cells can reach that ocean. The answer is the intersection. This reversal technique shows up any time forward simulation is expensive but backward simulation is cheap. It feels backwards the first time you see it. Then it feels obvious forever after.

Pattern 2: Graph Representation

4. Clone Graph (LC 133): The Cycle Problem Nobody Warns You About

A graph with arbitrary structure, cycles included. Deep copy it.

The visited hash map does double duty: it marks nodes as seen AND maps original nodes to their clones. Skip it and you infinite-loop on cycles. This problem forces you to write BFS or DFS on an explicit adjacency list graph rather than a convenient grid. Which is what most real graph problems look like. The grid is a crutch. This problem takes it away.

Pattern 3: Union-Find

5. Number of Provinces (LC 547): Learn This or Keep Rewriting BFS

For each edge, union the two endpoints. Count distinct components at the end. Simple.

This problem exists to teach you when Union-Find beats BFS/DFS. For a static graph, they're equivalent. Union-Find wins when edges arrive one at a time and you need fast connectivity queries after each insertion. Implement path compression and union by rank here. Don't implement the naive version. The naive version is a character flaw.

6. Redundant Connection (LC 684): Union-Find Doesn't Detect Cycles

Find the first edge that creates a cycle in an undirected graph.

Here's the misconception that kills candidates: they think Union-Find detects cycles. It doesn't. Union-Find checks whether two nodes are already in the same component. If they are and you're adding an edge between them, that edge is redundant. The cycle is a consequence, not a direct detection. This is also how Kruskal's MST algorithm filters out cycle-forming edges. Two problems, one insight.

Pattern 4: Topological Sort

Four Problems. Solve Them in Order. Don't Skip.

7. Course Schedule (LC 207): Two Ways to Find a Cycle

Can you finish all courses given prerequisites? Directed cycle detection.

Two approaches. DFS with three-color marking (white = unvisited, gray = in progress, black = done, a gray-to-gray back edge = cycle) or Kahn's BFS-based algorithm (if your processed node count is less than total nodes, a cycle exists somewhere). Learn both, because interviewers ask which one you prefer and why. Kahn's is usually cleaner to code under pressure. DFS-based is faster to explain conceptually. Know both answers.

8. Course Schedule II (LC 210): Same Graph, Now Return the Order

Same graph, now return a valid ordering.

Kahn's algorithm gives you the topological order directly: nodes enter the queue when their in-degree hits zero, and the dequeue order IS a valid topological sort. If the collected ordering has fewer nodes than total courses, a cycle exists. Detection and ordering in a single pass. Efficient. Elegant. Write it until it's muscle memory.

9. All Paths From Source to Target (LC 797): Free BFS, No Visited Set Needed

A guaranteed DAG. Find every path from node 0 to the last node.

Because there are no cycles, you don't need a visited set. Just DFS with backtracking. Append the current node to the path before recursing, pop it after returning. This is the bridge between graph problems and backtracking: same mechanics, different guarantees. A lot of candidates overthink this one. The constraint is the gift.

10. Alien Dictionary (LC 269): Build the Graph Yourself

The hardest in this group, and honestly a bit mean. The graph isn't given. You build it by comparing adjacent words in the sorted dictionary, extracting character ordering constraints one pair at a time. Then run topological sort on the character graph you just constructed.

This is a two-step pipeline: graph construction then topological sort. Both steps have bugs. Interviewers know both bugs. The construction bug: if a word appears before its own prefix in the list (e.g., "abc" before "ab"), the ordering is invalid. Return empty string immediately. The topological sort bug: if the graph has a cycle, also return empty. Practice both failure modes explicitly.

Pattern 5: State-Space BFS

11. Word Ladder (LC 127): This Is a Graph Problem. I Promise.

This doesn't look like a graph problem. Which is why it trips so many people. It is a graph problem.

Each word is a node. Two words are connected if they differ by exactly one letter. You never build the adjacency list explicitly. For each word you dequeue, try replacing each character position with every letter, and check if the result is in the word set. BFS on this implicit graph gives you the shortest transformation sequence.

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    wordSet = set(wordList)
    queue = deque([(beginWord, 1)])
    while queue:
        word, steps = 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 steps + 1
                if next_word in wordSet:
                    wordSet.remove(next_word)
                    queue.append((next_word, steps + 1))
    return 0

Turning states into nodes and transitions into edges is the most reusable move in graph interviews. Open the Lock, Jump Game IV, and Minimum Genetic Mutation all use it. Once you've done Word Ladder, you see the pattern everywhere. Before that, you just see a word problem and panic.

Pattern 6: Weighted Shortest Paths

12. Network Delay Time (LC 743): Classic Dijkstra's

Standard Dijkstra's: weighted directed graph, find how long it takes a signal to reach all nodes from a source. The answer is the maximum shortest-path distance across all nodes.

Pop from the min-heap, skip if already finalized, relax neighbors. A node is finalized the first time it's popped because the min-heap guarantees the smallest distance comes out first on non-negative weights. See the full Dijkstra breakdown for the correctness proof. Note: this only works with non-negative weights. One negative edge and Dijkstra gives wrong answers with no error message.

13. Cheapest Flights Within K Stops (LC 787): When Dijkstra Breaks

Now there's a hard constraint: at most K stops. This kills Dijkstra's greedy property. A longer path might be cheaper, but the heap would finalize the wrong node first. Dijkstra is greedy. Greedy fails here.

Use Bellman-Ford for K+1 iterations, and snapshot the distance array before each pass. The snapshot prevents same-pass cascades where a relaxation in round i feeds another relaxation in the same round, simulating more hops than the constraint allows.

def findCheapestPrice(n, flights, src, dst, k):
    prices = [float('inf')] * n
    prices[src] = 0
    for _ in range(k + 1):
        temp = prices[:]
        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 temp = prices[:] line is not cosmetic. Remove it and the algorithm gives wrong answers. Interviewers know this. The line is a trap. Don't fall in.

Pattern 7: Minimum Spanning Tree

14. Min Cost to Connect All Points (LC 1584): Algorithm Choice Matters

Given n points in a plane, connect all of them with minimum total Manhattan distance.

The graph is complete: every pair of points has an edge. Kruskal's would require generating and sorting all O(n²) edges first. That's O(n² log n) and it's the wrong choice. Prim's algorithm, using a simple array to track the cheapest edge into the growing tree, runs in O(n²) and wins on dense graphs. This is one of the rare problems where knowing which MST algorithm to pick actually changes your complexity analysis. Candidates who know only one MST algorithm get unlucky here.

Pattern 8: Bridge Finding

15. Critical Connections in a Network (LC 1192): Tarjan's Algorithm

Find every edge whose removal disconnects the graph. These are bridges.

Tarjan's algorithm finds all bridges in O(V+E) using two values per node: disc (discovery time in DFS) and low (minimum discovery time reachable from the subtree). An edge (u, v) is a bridge if low[v] > disc[u]. That strict inequality is the entire test.

This is the hardest algorithm on this list. It's a hard at FAANG. Read the full Bridges and Articulation Points breakdown before targeting that tier. And when your interviewer gives you this problem, at least you'll know why you're sweating.

How to Practice This List (Without Losing Your Mind)

Don't rotate through all fifteen in order. Work within one pattern group until you can code the solution from scratch without reference. Then move to the next.

The most common failure mode in graph interviews isn't forgetting an algorithm. It's solving the coding part in silence, without explaining why you chose this traversal over the alternatives. That narration is what the interviewer writes down. Correct and silent still fails.

If you want to train that skill, SpaceComplexity runs voice-based mock interviews where an AI interviewer probes your reasoning on graph problems in real time and scores your explanation alongside your code. The algorithm you get right in silence doesn't help you here. The one you explain clearly does.

Key Takeaways

The outer loop for disconnected components is mandatory. Forgetting it is the most common graph bug in interviews.
Multi-source BFS seeds multiple nodes at time zero. The algorithm doesn't change, just the initialization.
Union-Find checks component membership, not cycles. A cycle is a consequence, not a direct detection.
Word Ladder is the canonical state-space BFS. State = node, transition = edge. Once you see it, you can't unsee it.
The Bellman-Ford snapshot (temp = prices[:]) is mandatory for K-stop constraint problems. Non-negotiable.
Critical Connections requires Tarjan's bridge algorithm. Know disc vs low. Know the strict inequality.