Graph algorithms interview questions: BFS, DFS, topological sort and union-find

Graph interview questions test whether you can model a problem as nodes and edges and then pick the right traversal. Use BFS for the shortest path when every edge costs the same, DFS for connectivity and cycle detection, topological sort for ordering tasks with dependencies, union-find for merging groups, and Dijkstra when edges carry non-negative weights. Most of these run in O(V + E) time.

What counts as a graph problem?

Some prompts say "graph" outright: given a list of edges, find something. Many don't. The graph is hidden in the wording, and spotting it is half the question.

• Dependencies: courses with prerequisites, build steps, package installs. Each item is a node and each "must come before" is a directed edge.
• Grids: a map of land and water, a maze, a board. Each cell is a node with up to four neighbours.
• Transformations: change one letter at a time to turn one word into another. Each word is a node, and words one edit apart share an edge.
• Relationships: friends, accounts that share an email, cities joined by roads.
• States: a lock with four dials, a puzzle board. Each configuration is a node and each move is an edge.

How do you represent a graph in an interview?

Three representations come up. Pick one in a sentence and move on.

• Adjacency list: a dictionary or list mapping each node to its neighbours. Space is O(V + E), and iterating a node's neighbours is fast. This is the default for interview problems.
• Adjacency matrix: a V by V grid of booleans or weights. Checking whether one edge exists is O(1), but space is O(V²), which is wasteful for sparse graphs.
• Edge list: a plain list of pairs. Fine as input, and the natural format for union-find and for sorting edges by weight, but slow for finding neighbours.

Most prompts hand you an edge list, so the first few lines of code usually build an adjacency list from it. Say whether the graph is directed or undirected. For undirected edges, add each edge in both directions. Forgetting that is one of the most common bugs.

BFS for the shortest path in an unweighted graph

Breadth-first search visits nodes in order of distance from the start: everything one edge away, then two, then three. That means the first time BFS reaches a node, it has found a shortest path to it, as long as every edge has the same cost.

from collections import deque

def shortest_path(graph, start, goal):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            return dist[node]
        for nxt in graph[node]:
            if nxt not in dist:      # mark on enqueue, not on dequeue
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return -1

graph = {"a": ["b", "c"], "b": ["d"], "c": ["d", "e"], "d": ["f"], "e": ["f"], "f": []}
print(shortest_path(graph, "a", "f"))  # 3
print(shortest_path(graph, "f", "a"))  # -1

The comment matters. Mark a node as seen when you add it to the queue, not when you remove it. Otherwise the same node can be queued many times by different neighbours, which wastes time and, on dense graphs, memory. The function returns -1 when the goal can't be reached, which you should test explicitly. Time is O(V + E) and space is O(V).

BFS also answers level questions: the minimum number of moves, the fewest transformations, the nodes at distance k. Multi-source BFS starts with several nodes in the queue at once, which is how you compute the distance from every cell to the nearest exit in one pass.

DFS and cycle detection

Depth-first search goes as far as it can along one path before backing up. It doesn't find shortest paths, but it is the natural tool for exploring connected regions, finding paths that exist, and detecting cycles. You can write it recursively or with an explicit stack. In Python the explicit stack is safer for large inputs, because the default recursion limit is 1,000 frames.

Cycles in an undirected graph

During DFS, if you reach a neighbour that is already visited and is not the node you just came from, there is a cycle. Union-find gives a second way: if an edge joins two nodes that already share a root, that edge closes a cycle.

Cycles in a directed graph

A visited neighbour is not enough in a directed graph, because two paths can meet without forming a loop. Use three states. Unvisited, in progress (on the current DFS path) and done. Reaching a node that is in progress means you have found a back edge, which is a cycle. Reaching a node that is done is fine.

Topological sort with Kahn's algorithm

A topological order lists the nodes of a directed graph so that every edge points forward. It exists only when the graph has no cycles. Course schedules, build orders and task pipelines all ask for one.

Kahn's algorithm counts incoming edges for every node, starts with the nodes that have none, and repeatedly removes a node and decrements its neighbours' counts. Any neighbour that drops to zero joins the queue.

from collections import deque

def topo_order(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for before, after in edges:
        graph[before].append(after)
        indegree[after] += 1
    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == n else []  # [] means a cycle

print(topo_order(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))  # [0, 1, 2, 3]
print(topo_order(2, [(0, 1), (1, 0)]))                  # []

If a cycle exists, the nodes on it never reach zero incoming edges, so the output comes up short. Comparing the length of the order with n is the cycle check, and it is why "can you finish all courses?" and "give a valid course order" are the same problem. Time is O(V + E).

The DFS alternative records each node when its DFS finishes and reverses that list at the end. Both are correct. Kahn's algorithm is often easier to explain in an interview because the cycle check falls out naturally and there is no recursion.

Union-find for connected groups

Union-find, also called disjoint set union, keeps track of which nodes belong to the same group. It supports two operations: find, which returns a group's representative, and union, which merges two groups. It shines when edges arrive one at a time and you only care about connectivity.

def count_components(n, edges):
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path halving
            x = parent[x]
        return x

    components = n
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            components -= 1
    return components

print(count_components(5, [(0, 1), (1, 2), (3, 4)]))  # 2

Every successful union merges two groups, so the component count drops by one. Path halving makes later finds shorter. With union by size or rank added, both operations run in near-constant amortized time. Path compression alone is usually fast enough for interview inputs, and it is worth saying which version you wrote.

Typical uses: counting connected components, finding the redundant edge that creates a cycle, merging accounts that share an email, and Kruskal's minimum spanning tree. Union-find can't delete edges or tell you the path between two nodes, so reach for BFS or DFS when you need those.

Dijkstra's algorithm in brief

When edges have different non-negative weights, BFS no longer finds the shortest path, because a route with more edges can cost less. Dijkstra's algorithm replaces the queue with a min-heap ordered by distance so far. Pop the closest unfinished node, then relax each edge: if going through this node gives a neighbour a shorter distance, record it and push the neighbour onto the heap.

In Python, heapq does the work. The usual shortcut is lazy deletion: push a new entry whenever a distance improves, and skip popped entries whose distance is larger than the best one recorded. With a binary heap the run time is O((V + E) log V). Dijkstra fails with negative edge weights. If the interviewer adds them, mention Bellman-Ford, which handles negative edges in O(V × E) and can detect negative cycles.

Grids as graphs: number of islands

Number of islands is the classic hidden graph. You get a grid of "1" for land and "0" for water and must count the connected land regions. Each cell is a node, and its up, down, left and right neighbours are its edges. Scan every cell, and each time you find unvisited land, flood-fill its whole island and add one to the count.

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()

    def sink(r, c):
        stack = [(r, c)]
        while stack:
            r, c = stack.pop()
            if (r, c) in seen or not (0 <= r < rows and 0 <= c < cols):
                continue
            if grid[r][c] != "1":
                continue
            seen.add((r, c))
            stack.extend([(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)])

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                sink(r, c)
                count += 1
    return count

print(num_islands(["110", "100", "011"]))  # 2

This version uses an explicit stack, so a large island can't hit the recursion limit, and it checks bounds before reading the grid. Each cell is processed a constant number of times, so time is O(rows × cols), and the seen set adds up to the same in space. If you are allowed to modify the input, overwrite visited land with "0" and drop the set. Ask before you do, because mutating input is a choice the interviewer may want to discuss.

Many grid problems are this one in a different coat: the largest island, the number of enclosed regions, rotting oranges (multi-source BFS), or the shortest path through a maze (plain BFS).

Complexity to state for common graph algorithms

Interviewers expect you to give complexity in terms of V nodes and E edges. These are the figures to know.

• BFS and DFS with an adjacency list: O(V + E) time, O(V) extra space.
• BFS or DFS on an r by c grid: O(r × c) time and space.
• Topological sort, Kahn's or DFS: O(V + E) time.
• Union-find with path compression and union by rank: near-constant amortized time per operation.
• Dijkstra with a binary heap: O((V + E) log V) time.
• Bellman-Ford: O(V × E) time.
• Adjacency matrix storage: O(V²) space, whatever the number of edges.

Worked example: talking through course schedule

Here is an invented example of a candidate's narration for "given n courses and prerequisite pairs, can you finish them all?"

"Each course is a node and each prerequisite is a directed edge from the prerequisite to the course. Finishing everything means there's an order where every edge points forward, so this is topological sort, and it fails exactly when there's a cycle. I'll use Kahn's algorithm. Count incoming edges, queue the courses with none, and keep removing. If I process all n courses, the answer is yes. If some are left, they're stuck in a cycle. That's O(V plus E). I'll test a simple chain, a two-course cycle, and a course with no prerequisites at all."

It names the nodes and edges first, ties the question to a property (no cycles), and picks tests for yes, no and an isolated node. A common follow-up, "now return the order", is already answered.

Common mistakes

1. Adding undirected edges in one direction only. Half the graph goes missing and traversals stop early. Add both directions.
2. Marking visited too late in BFS. Mark on enqueue. Marking on dequeue lets duplicates fill the queue.
3. Using the undirected cycle rule on a directed graph. A visited neighbour is not a cycle in a directed graph. Use the three-state rule or Kahn's count.
4. Using BFS on weighted edges. BFS counts edges, not cost. Different weights need Dijkstra.
5. Forgetting disconnected parts. Start a traversal from every unvisited node, not only from node 0, or isolated components are never counted.
6. Recursing on a huge grid. Python's recursion limit can end a recursive flood fill. Use an explicit stack or a queue.

A practice loop for graph questions

Practice recognising the model separately from the coding.

1. Model before you code. For each problem, say what the nodes are, what the edges are, whether they're directed, and whether they're weighted. Then name the algorithm.
2. Write the four templates from memory. BFS, iterative DFS, Kahn's algorithm and union-find. Each fits in about fifteen lines. Rewrite them until they come out cleanly.
3. Solve one problem per template, aloud, on a timer. Twenty-five minutes, with narration, as you would in the round.
4. Mix them up. Once each template is solid, pick problems without knowing the category in advance. Recognition is the skill being tested.
5. Review complexity every time. Say O(V + E) and what V and E are for this specific problem.

Practice graph problems on the Live coding surface

HIDEA AI keeps four separate surfaces: Verbal, Live coding, System design and Project. Graph practice belongs on Live coding. You capture the problem from the screen, and the response leads with a plain-English approach, then code in your chosen language, then time and space complexity.

A useful habit is to model the graph yourself first: say the nodes, the edges and the algorithm, write your solution, then check your complexity statement against the response. You still speak or type every answer. Fifteen session minutes a day is free, with no credit card, in the desktop app for macOS and Windows. The interview copilot overview explains each surface, and the setup guide walks through the first run.

If you plan to use any tool in a real coding round, check the employer's rules first. Some publish them, and what some employers publish collects examples.

Where to go next

• See how graphs fit with the other shapes: coding interview patterns.
• The other big family of hard problems: dynamic programming interview patterns.
• Rehearse the clock and the narration: live coding mock interview: narrate under a timer.
• Download the app and run one graph problem today.