Graph search

A tree is a graph with no cycles and one way down. Real graphs have cycles, several paths between the same two nodes, and pieces that don’t connect at all. Interview graphs rarely say “graph” either: they’re a grid of land and water, a list of course prerequisites, a set of words one letter apart. Most of the work is seeing the graph: what the nodes are, and what counts as an edge.

Once you see it, three tools cover nearly every interview question. BFS finds shortest paths when every edge costs the same. DFS explores everything reachable, which is what counting islands and finding connected pieces need. Topological sort orders tasks so every prerequisite comes first, and tells you when that’s impossible.

What makes this hard

• Model it first: nodes, edges, directed or not. A grid is a graph whose edges are the four (or eight) neighbors.
• Keep a visited set on every graph search. Unlike trees, graphs have cycles, and without it the search never ends.
• BFS with a queue reaches nodes in order of distance, so the first visit is a shortest path in an unweighted graph.
• DFS with recursion or a stack goes deep first. Use it for reachability, components and cycle detection.
• Topological sort (Kahn’s algorithm) repeatedly takes nodes with no remaining prerequisites. If some are never taken, there’s a cycle.

How to spot it

• A grid with cells to visit: islands, flood fill, rotting oranges, a maze.
• “Fewest steps”, “shortest path”, “minimum moves” with no weights: BFS.
• “Connected”, “reachable”, “how many groups”: DFS or BFS, either works.
• Prerequisites, dependencies, build order, “can all tasks finish?”: topological sort on a directed graph.
• States that change one step at a time, such as words one letter apart, or lock combinations. Each state is a node, and BFS finds the fewest steps.

Weighted edges are a different problem. When edges have different costs, BFS’s “first visit is shortest” stops being true. Then you need Dijkstra’s algorithm. It’s a BFS whose queue is a heap ordered by distance.

Watch it run

BFS from A. The queue hands out nodes in the order they were found, which is the order of their distance. Everything 1 hop away comes before anything 2 hops away. When a node is reached for the first time, it gets its distance, and it never changes. The green edges are the shortest-path tree.

BFS distancesTopological sort

queue front → back

A

1. distance = {start: 0}
2. queue = deque([start])
3. while queue:
4. node = queue.popleft()
5. for neighbor in graph[node]:
6. if neighbor not in distance:
7. distance[neighbor] = distance[node] + 1
8. queue.append(neighbor)

Shortest number of hops from A to every node. A is 0 hops away and waits in the queue.

← BackStep →Play1 / 9

Switch to Topological sort. The arrows point from a prerequisite to the node that needs it, and in counts how many prerequisites are still unmet. Nodes with none are ready. Taking a node removes one prerequisite from each node it points to, and any node that reaches 0 becomes ready.

The template

BFS distances, counting islands with an iterative DFS, and topological sort:

JGraphSearch.javaPyexample.pyC#GraphSearch.csGomain.goTSexample.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class GraphSearch {
    static Map<String, Integer> bfsDistances(Map<String, List<String>> graph, String start) {
        // Fewest edges from start to every reachable node. The queue releases nodes in order
        // of distance, so the first time we reach a node is along a shortest path. Mark nodes
        // when they are queued, not when taken, or a node can be queued many times.
        Map<String, Integer> distance = new HashMap<>(Map.of(start, 0));
        ArrayDeque<String> queue = new ArrayDeque<>(List.of(start));
        while (!queue.isEmpty()) {
            String node = queue.poll();
            for (String neighbor : graph.get(node)) {
                if (!distance.containsKey(neighbor)) {
                    distance.put(neighbor, distance.get(node) + 1);
                    queue.add(neighbor);
                }
            }
        }
        return distance;
    }

    static int countIslands(char[][] grid) {
        // Every land cell we start a search from, that no earlier search reached, is a new
        // island. An explicit stack instead of recursion, so a huge island can't overflow the
        // call stack. Visited land is sunk to '0' in place; copy the grid first if you can't.
        int[][] steps = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int islands = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[row].length; column++) {
                if (grid[row][column] != '1') continue;
                islands++;
                grid[row][column] = '0';
                ArrayDeque<int[]> stack = new ArrayDeque<>();
                stack.push(new int[] {row, column});
                while (!stack.isEmpty()) {
                    int[] cell = stack.pop();
                    for (int[] d : steps) {
                        int nextRow = cell[0] + d[0], nextColumn = cell[1] + d[1];
                        if (nextRow >= 0 && nextRow < grid.length && nextColumn >= 0
                            && nextColumn < grid[nextRow].length
                            && grid[nextRow][nextColumn] == '1') {
                            grid[nextRow][nextColumn] = '0';
                            stack.push(new int[] {nextRow, nextColumn});
                        }
                    }
                }
            }
        }
        return islands;
    }

    static List<Integer> topoOrder(int nodeCount, int[][] edges) {
        // Kahn's algorithm. Edge {a, b} means a must come before b. A node is ready once every
        // node pointing at it is done. Nodes that never become ready sit on a cycle, and then
        // no valid order exists: return an empty list.
        List<List<Integer>> out = new ArrayList<>();
        for (int i = 0; i < nodeCount; i++) out.add(new ArrayList<>());
        int[] inDegree = new int[nodeCount];
        for (int[] edge : edges) {
            out.get(edge[0]).add(edge[1]);
            inDegree[edge[1]]++;
        }
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < nodeCount; i++) if (inDegree[i] == 0) queue.add(i);
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int neighbor : out.get(node)) if (--inDegree[neighbor] == 0) queue.add(neighbor);
        }
        return order.size() == nodeCount ? order : List.of();
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = Map.of(
                "A", List.of("B", "C"), "B", List.of("A", "D"), "C", List.of("A", "D", "E"),
                "D", List.of("B", "C", "F"), "E", List.of("C", "F"), "F", List.of("D", "E", "G"),
                "G", List.of("F"));
        check(bfsDistances(graph, "A").equals(Map.of("A", 0, "B", 1, "C", 1, "D", 2, "E", 2, "F", 3, "G", 4)));
        char[][] grid = {"11000".toCharArray(), "11011".toCharArray(), "00010".toCharArray(), "10000".toCharArray()};
        check(countIslands(grid) == 3);
        check(topoOrder(4, new int[][] {{0, 1}, {0, 2}, {1, 3}, {2, 3}}).equals(List.of(0, 1, 2, 3)));
        check(topoOrder(3, new int[][] {{0, 1}, {1, 2}, {2, 0}}).isEmpty()); // a cycle has no order
        System.out.println("ok: bfsDistances, countIslands and topoOrder");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

Three decisions shape every graph solution:

• How to store the graph. Usually an adjacency list: a map or array from each node to its neighbors. Build it from an edge list first. For grids, don’t build anything: compute the neighbors from the row and column.
• When to mark visited. Mark a node when you add it to the queue or stack, not when you take it out. Otherwise the same node can be added many times before it’s processed, and on a dense graph the queue explodes.
• Whether you can change the input. Sinking land to water in place is a neat way to mark visited cells. But say so first. Some interviewers want the input left alone, and then you need a separate visited set.

Multi-source BFS

Rotting oranges asks how many minutes until every orange rots, when each rotten one spreads to its neighbors every minute. Start the BFS with every rotten orange in the queue at distance 0. The levels of the BFS are then the minutes, and the answer is the last level reached. Walls and gates and “distance to nearest 0” work the same way.

Cycle detection

In an undirected graph, DFS finds a cycle when it reaches a visited node that isn’t the one it just came from. In a directed graph, a visited node isn’t enough, since two paths can reach the same node without a cycle. You need three states: unvisited, on the current path, and done. A cycle is an edge to a node still on the current path. Kahn’s algorithm avoids all this: if the order it produces is shorter than the number of nodes, there’s a cycle.

TradeoffBFS vs DFS when either works

We gain

BFS gives shortest paths for free and never recurses, so it can’t overflow the call stack.

We give up

BFS holds a whole frontier in its queue, which on a wide graph is much more memory than DFS’s single path. DFS is often shorter to write recursively, and it’s what cycle detection and some ordering problems need.

Complexity

Every algorithm here visits each node once, and looks at each edge once (twice if undirected). So time is O(V + E), for V nodes and E edges. For a grid of R × C cells, that’s O(R × C), since each cell has at most four edges. Memory is O(V), for the visited set and the queue or stack.

Common mistake

Marking a node visited when you dequeue it

With visited.add(node) after queue.popleft(), a node can be enqueued once by every neighbor that sees it before it’s processed. Results are still correct, but in a grid the queue can hold the same cell four times, and in a dense graph far more. Mark nodes at the moment you enqueue them.

Say this out loud

Each cell is a node and its four neighbors are its edges. Every edge costs one step, so BFS finds the fewest steps. It visits each cell once: O(rows × columns).

Interview questions

Interviewer asksNumber of islands: DFS or BFS? Recursive or iterative?

Either search works, and both are O(R × C). Recursive DFS is shortest to write. But one island covering a 1000 × 1000 grid recurses a million deep, and overflows the stack in most languages. An explicit stack or a queue avoids that. Mention the limit, then pick iterative if the grid can be large. Union-find is a third option. It’s the right one if land is added cell by cell over time.

Interviewer asksCourse schedule: how do you know if all courses can be finished?

Courses are nodes, and each prerequisite is a directed edge. All of them can be finished exactly when the graph has no cycle. Run Kahn’s algorithm: if every course ends up in the order, it’s possible, and the order is a valid schedule. If some never reach in-degree 0, they’re waiting on each other in a cycle.

Interviewer asksWord ladder is slow on a large dictionary. How do you speed it up?

Finding neighbors by comparing every pair of words is O(N² × L). Instead, for each word, try all 26 letters at each of its L positions, and look the result up in a set. That’s O(26 × L) per word. A second speedup is bidirectional BFS. Search from both ends, and stop when the frontiers meet. Each side then only needs to go about half the depth, which shrinks the frontiers a lot.

Practice

10 problems on LeetCode: 1 easy, 8 medium, 1 hard

1. Flood Fill↗(opens LeetCode in a new tab)

   DFS from the start cell over neighbors with the same color.

   Easy
2. Number of Islands↗(opens LeetCode in a new tab)

   Each DFS that starts on unvisited land is one island.

   Medium
3. Max Area of Island↗(opens LeetCode in a new tab)

   The same DFS as islands, returning the size it covered.

   Medium
4. Clone Graph↗(opens LeetCode in a new tab)

   A map from original to copy doubles as the visited set.

   Medium
5. Rotting Oranges↗(opens LeetCode in a new tab)

   Multi-source BFS: every rotten orange starts in the queue.

   Medium
6. Pacific Atlantic Water Flow↗(opens LeetCode in a new tab)

   Search uphill from each ocean, then intersect.

   Medium
7. Shortest Path in Binary Matrix↗(opens LeetCode in a new tab)

   Unweighted shortest path means BFS, with eight neighbors.

   Medium
8. Course Schedule↗(opens LeetCode in a new tab)

   A valid order exists only if the prerequisite graph has no cycle.

   Medium
9. Course Schedule II↗(opens LeetCode in a new tab)

   Kahn's algorithm returns the order it took courses in.

   Medium
10. Word Ladder↗(opens LeetCode in a new tab)

    Words are nodes, one-letter changes are edges, and BFS finds the shortest chain.

    Hard

Ticks are saved in this browser only. Clear your site data and they're gone.

Recap

• Model first: what are the nodes, what are the edges, are they directed?
• Use BFS for shortest paths with equal edge costs. Use DFS for reachability and components. Use Kahn’s algorithm for dependency order and cycle checks.
• Always track visited, and mark when you enqueue or push.
• Grids are graphs: compute neighbors from the row and column.
• Cost: O(V + E) time, O(V) memory. Prefer iterative search when the graph can be deep.