Graph Interview Questions: A Practical Walkthrough

Most graph interview questions reduce to a small set of algorithms: BFS, DFS, topological sort, Dijkstra, and a union-find or minimum spanning tree variant. The hard part is not memorizing them. It is recognizing which one a problem wants when the word "graph" never appears. This walkthrough covers the five algorithms worth drilling, the cues that map a problem to each, and a full worked example at the staff level so you can see how the pieces fit under time pressure.

We run mock interviews all day, and graphs are where we see the widest gap between candidates who "know the algorithm" and candidates who can actually ship a correct solution in 25 minutes. The difference is almost always pattern recognition and clean state management, not raw algorithm knowledge.

The five algorithms that cover most interviews

If you learn these five well, you can attack the large majority of graph problems you will see. The advice we agree with is to practice in order: start with BFS and DFS, because they are the foundation the others build on.

Algorithm	Use it when	Typical cost
BFS	Shortest path in an unweighted graph, level-by-level exploration	O(V + E)
DFS	Connected components, cycle detection, exhausting one branch first	O(V + E)
Topological sort	Ordering with prerequisites or dependencies (DAG only)	O(V + E)
Dijkstra	Shortest path with non-negative edge weights	O((V + E) log V)
Union-Find / MST	Grouping, connectivity, "minimum cost to connect everything"	Near O(E log E)

The mapping is mechanical once you internalize it. BFS is for exploring nodes level by level or finding the shortest path in unweighted graphs, while DFS fits exploring a branch fully, which is why it underpins topological sorting, connected components, and backtracking. For weighted shortest paths, the standard move is Dijkstra with a priority queue: distance to the start is 0 and everything else is infinity, then you repeatedly extract-min and relax edges, giving O((V + E) log V).

Two clarifications candidates trip on:

Dijkstra breaks with negative edge weights. If an interviewer sneaks in negatives, you need Bellman-Ford instead. Say this out loud; it is a signal.
Topological sort only exists on a directed acyclic graph. If a cycle is possible, part of the problem is usually detecting it.

If you want a structured list of graph problems to grind through, our Graph Theory question set is organized by exactly these patterns.

How to recognize a graph problem when it is disguised

Interviewers rarely hand you an adjacency list and say "run BFS." The skill they are testing is modeling. The single most common disguise is a grid. A 2D grid is a graph where each cell is a node and adjacent cells are edges, which makes grid problems the most common disguised graph problem you will see.

Here are the phrase-to-algorithm cues we drill with candidates:

"Shortest path" with no weights, or "fewest steps" -> BFS.
"Prerequisites," "dependencies," "build order," "course schedule" -> topological sort.
"Minimum cost to connect all," "cheapest way to link" -> minimum spanning tree.
"Are these two things connected," "number of groups/islands/provinces" -> DFS flood fill or union-find.
"Cheapest path" with weights -> Dijkstra.

"Shortest path" without weights points to BFS, "prerequisites" or "dependencies" points to topological sort, and "minimum cost to connect" points to MST. Train yourself to translate the problem statement into "nodes are X, edges are Y" as the first thing you say. That one sentence buys you time and shows structured thinking.

Cycle detection is the other reusable subroutine. For an undirected graph you run DFS and flag a cycle if you reach an already-visited node that is not the parent, or you use a disjoint set: for each edge, union the endpoints, and if an edge connects two nodes already in the same set, a cycle exists.

A minimal BFS template you should be able to write without thinking:

from collections import deque

def bfs_shortest(start, target, neighbors):
    q = deque([(start, 0)])
    seen = {start}
    while q:
        node, dist = q.popleft()
        if node == target:
            return dist
        for nxt in neighbors(node):
            if nxt not in seen:
                seen.add(nxt)          # mark on enqueue, not dequeue
                q.append((nxt, dist + 1))
    return -1

The one bug we see constantly: marking a node visited when you dequeue it instead of when you enqueue it. That lets the same node get queued multiple times and quietly breaks correctness on larger inputs. Mark on enqueue.

If BFS and DFS are shaky, work through them side by side in our BFS question set and DFS question set before touching the weighted algorithms.

A worked example: minimum spanning tree and critical edges

Let's take a genuinely hard one from our bank: Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree (staff level). You are given a weighted undirected connected graph and an edge list edges[i] = [a, b, weight]. A critical edge is one that appears in every MST; removing it increases the total MST weight or disconnects the graph. A pseudo-critical edge appears in some MST but not all.

This problem is a clean test of whether you actually understand MST, not just how to run Kruskal. Here is the approach we coach:

Sort edges by weight and compute the baseline MST weight with Kruskal plus union-find. This is your reference number.
For each edge, test if it is critical: skip that edge entirely and rebuild the MST. If you cannot connect all nodes, or the resulting weight is larger than the baseline, the edge is critical.
If it is not critical, test if it is pseudo-critical: force that edge into the tree first (union its endpoints, add its weight), then run Kruskal on the rest. If the total still equals the baseline, the edge can belong to some MST, so it is pseudo-critical.

The complexity is O(E^2 * alpha(V)) in the worst case because you rerun Kruskal per edge, which is fine for interview constraints. The insight interviewers reward is the two independent tests (exclude to check critical, include to check pseudo-critical) built on one reusable union-find. If you can articulate why forcing inclusion and comparing against the baseline detects "belongs to some MST," you have demonstrated real understanding.

This is also a good reminder that union-find is not a niche trick. It is the backbone of Kruskal, connectivity queries, and cycle detection, and it shows up far more often than most candidates expect.

How to practice so it holds up under pressure

Reading solutions creates the illusion of competence. The habit that actually works is to implement each algorithm from scratch, write it and debug it yourself rather than just reading the code. Then add the constraint that matters. In interviews you get roughly 20 to 30 minutes per problem, so practice with a timer and get comfortable working under that constraint.

A concrete plan that we have seen move people from "I freeze on graphs" to "I can pattern-match in 60 seconds":

Week 1: BFS and DFS on both grids and adjacency lists. Number of islands, flood fill, shortest path in a maze.
Week 2: Topological sort and cycle detection. Course schedule variants, build order.
Week 3: Weighted shortest paths (Dijkstra) and MST (Kruskal, Prim, union-find), including the critical-edges problem above.
Ongoing: one timed rep per day where you say the model out loud ("nodes are cells, edges are adjacent cells") before writing anything.

The reason to say the model out loud is that graph interviews are as much about communication as code. Interviewers score whether you narrate your reasoning, and a wrong-but-well-explained approach often beats a silent correct one on the rubric. Running full graph reps against an interviewer that talks back, like our AI mock interviews, is the fastest way to close the gap between knowing the algorithm and performing it.

FAQ

What is the most important graph algorithm to learn first?

BFS and DFS, without question. They cover connected components, unweighted shortest paths, cycle detection, and flood fill, and every other graph algorithm builds on the traversal logic they teach. Get both solid on grids and adjacency lists before touching Dijkstra or MST.

How do I know whether to use BFS or DFS?

Use BFS when you need the shortest path in an unweighted graph or want to explore level by level. Use DFS when you need to exhaust one path fully, such as connected components, topological ordering, or backtracking. When either would work, pick the one with simpler state management for that problem.

Are grid problems considered graph problems?

Yes. A grid is a graph where each cell is a node and adjacent cells are edges. Most "grid" problems (islands, rotting oranges, shortest path in a maze) are graph traversals in disguise, which is exactly why practicing them sharpens your graph pattern recognition.

When does Dijkstra fail, and what do I use instead?

Dijkstra assumes non-negative edge weights. If the graph can have negative edges, use Bellman-Ford, which also detects negative cycles. Flagging this trade-off unprompted is a strong signal in a senior or staff interview.

How much graph theory do I need for a coding interview?

For most software roles, the five patterns in this article are enough: BFS, DFS, topological sort, Dijkstra, and union-find/MST. Advanced topics like strongly connected components, network flow, or lowest common ancestor appear mainly at the staff level or in specialized teams, so prioritize the core five first.