Graph BFS / DFS

How does Graph BFS / DFS work?

Put the start node in a container and mark it seen. The container is a queue or a stack.

Take one node out of it. Look at every neighbour that node has.

Skip any neighbour that is already marked. That check is what stops the walk from looping.

Mark each new neighbour and put it in the container. Mark on entry, never on removal.

A queue takes the oldest node, so the walk spreads level by level. That gives the fewest edges to each node.

A stack takes the newest, so the walk drives deep first. Both visit every reachable node once.

1. queue = [1], seen = {1}Edges are 1-2, 1-3 and 2-4. The start is marked first.
2. take 1, queue = [2, 3]Both neighbours are new. They are marked as they enter.
3. take 2, queue = [3, 4]Node 4 is new. Node 1 is marked already and skipped.
4. take 3, queue = [4]Node 3 has no unmarked neighbours.
5. take 4, queue = []Nothing is left. Four nodes, each visited once.

function bfsDistances(adj, source) {
    const dist = { [source]: 0 };
    const queue = [source];
    while (queue.length) {
        const node = queue.shift();
        for (const next of adj[node] || []) {
            if (!(next in dist)) {
                dist[next] = dist[node] + 1;
                queue.push(next);
            }
        }
    }
    return dist;
}

A worked example of Graph BFS / DFS

How long until every orange rots

A grid holds empty cells, fresh oranges and rotten ones. Each minute a rotten orange rots its four neighbours.

Return the minutes until nothing fresh is left, or minus one.

Every rotten orange goes into the queue before the walk starts.

Process one whole level of the queue per minute. A fresh orange left at the end means minus one.

function orangesRotting(grid) {
    const rows = grid.length;
    const cols = grid[0].length;
    let queue = [];
    let fresh = 0;

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 2) queue.push([r, c]);
            if (grid[r][c] === 1) fresh++;
        }
    }

    const steps = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    let minutes = 0;

    while (queue.length && fresh > 0) {
        const next = [];

        // one whole level per minute
        for (const [r, c] of queue) {
            for (const [dr, dc] of steps) {
                const nr = r + dr;
                const nc = c + dc;
                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                if (grid[nr][nc] !== 1) continue;

                grid[nr][nc] = 2; // marked on entry, so it is queued once
                fresh--;
                next.push([nr, nc]);
            }
        }

        queue = next;
        minutes++;
    }

    return fresh === 0 ? minutes : -1;
}

When should you use Graph BFS / DFS?

These phrases in a problem statement point here:

• •shortest path in an unweighted graph
• •fewest steps/hops between nodes
• •can node X reach node Y
• •explore ring by ring / layer by layer
• •graph given as adjacency list, may contain cycles

What is Graph BFS / DFS confused with?

• Tree traversal: A tree cannot reach a node twice, so it needs no visited set. A graph can, so it always does.
• Dijkstra's algorithm: Weighted edges break the level order. A heap then replaces the queue.
• Connected components: That page counts the groups in a graph. This is the walk that each count is built from.
• Backtracking: Backtracking undoes its state on the way out. A traversal marks a node and never unmarks it.

Common mistakes with Graph BFS / DFS

• Marking on removal instead of entry

  The same node then enters the queue many times over. Mark it at the moment you push it.

• Using a stack when the answer is a distance

  Depth-first can reach a node the long way round. Only a queue gives the fewest edges.

• Calling shift on a long queue

  In JavaScript shift is O(n) on an array. Use a read index or a level list instead.

• Forgetting the graph can be disconnected

  One walk only reaches one component. Loop over every node that is still unvisited.

Which interview problems use Graph BFS / DFS?

• Number of islands: One walk per unvisited land cell.
• Rotting oranges: Every rotten cell starts in the queue together.
• Word ladder: Words are nodes and one-letter edits are edges.
• Clone graph: The visited map also holds the copies made so far.
• Shortest path in a binary matrix: Eight directions, one queue, level counting.
• Course schedule: Detect a cycle in a directed graph.
• Pacific Atlantic water flow: Two walks, both started from the edges.

What is the time and space complexity of Graph BFS / DFS?

O(V+E)

V nodes and E edges give O(V + E). Memory is O(V) for the visited set and the frontier.