BFS and DFS

You’ll recognise it when

• The input is a graph, a grid, or anything where you can say “from here you can go to there”: rooms, word ladders, states of a puzzle.
• BFS: the question asks for the fewest moves, steps, minutes or hops, and every move costs the same. Also anything that spreads one ring at a time, like fire or rot.
• DFS: the question asks whether something is reachable, how many separate regions there are, whether there’s a cycle, or wants a path or an ordering (topological sort).
• Counting islands, filling a region, or cloning a graph: either works, so pick the one you write fastest.

If edges have different weights, neither gives shortest paths: that’s Dijkstra’s algorithm.

The idea

Drop a stone in a pond. The ripple reaches everything 1 metre away, then everything 2 metres away, and so on. That’s breadth-first search: it finishes every node at distance 1 before touching any node at distance 2, so the first time it reaches a node, it has found the fewest-edge route there.

Now explore a maze with one hand on the wall. You follow one corridor as far as it goes, and only at a dead end do you back up to the last junction with an unexplored branch. That’s depth-first search.

The two share one loop. Keep a frontier of nodes you’ve found but not explored, take one out, and add its new neighbours. The only difference is which one you take out. A queue hands back the oldest node, which gives BFS. A stack hands back the newest, which gives DFS.

How it works

The graphic runs BFS from node 0 on a graph of 10 nodes. Nodes sit in columns by their distance from 0, and node 9 isn’t connected to anything. Scroll through the steps and the graphic follows along.

Why the distances are right: nodes leave the queue in order of distance. When a node at distance d finds an unseen neighbour, every node at distance d - 1 or less has already been explored, and none of them reached it. So d + 1 is the fewest edges possible.

Now open edit and change mode to dfs. Same graph, same start. The queue becomes a stack, and the walk changes completely: 0, 1, 4, 2, 5, 7, 8, 6, 3 instead of 0 through 8 in order. The green discovery edges snake through the graph instead of fanning out. The DFS loop:

• Pop node from the top of the stack. If it’s already visited, skip it: that’s a stale copy.
• Otherwise mark it visited, add it to the order, and push its unvisited neighbours in reverse, so the first-listed neighbour ends up on top and is explored first. That makes the order match a recursive DFS.

DFS marks nodes when they come off the stack, which lets a node sit on the stack more than once (watch 2, 3 and 7 in the graphic). You can mark on push instead, like BFS, and it still reaches every node, but the order is then no longer depth-first.

from collections import deque


def bfs(adj, start):
    """Fewest edges from start to every node; -1 if unreachable."""
    dist = [-1] * len(adj)
    dist[start] = 0
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in adj[node]:
            if dist[nxt] != -1:
                continue                    # seen already: queued or done
            dist[nxt] = dist[node] + 1
            queue.append(nxt)               # mark when enqueued, not later
    return dist


def dfs(adj, start):
    """Nodes in the order a depth-first search first reaches them."""
    visited = [False] * len(adj)
    order = []
    stack = [start]
    while stack:
        node = stack.pop()
        if visited[node]:
            continue
        visited[node] = True
        order.append(node)
        # Reversed, so the first neighbour in adj ends up on top.
        for nxt in reversed(adj[node]):
            if not visited[nxt]:
                stack.append(nxt)
    return order


def build_graph(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:                      # undirected: store both ways
        adj[u].append(v)
        adj[v].append(u)
    return adj

#include <deque>
#include <utility>
#include <vector>
using namespace std;

// Fewest edges from start to every node; -1 if unreachable.
vector<int> bfs(const vector<vector<int>>& adj, int start) {
    vector<int> dist(adj.size(), -1);
    dist[start] = 0;
    deque<int> queue = {start};
    while (!queue.empty()) {
        int node = queue.front();
        queue.pop_front();
        for (int nxt : adj[node]) {
            if (dist[nxt] != -1) continue;
            dist[nxt] = dist[node] + 1;
            queue.push_back(nxt);               // mark when enqueued, not later
        }
    }
    return dist;
}

// Nodes in the order a depth-first search first reaches them.
vector<int> dfs(const vector<vector<int>>& adj, int start) {
    vector<bool> visited(adj.size(), false);
    vector<int> order;
    vector<int> stack = {start};
    while (!stack.empty()) {
        int node = stack.back();
        stack.pop_back();
        if (visited[node]) continue;
        visited[node] = true;
        order.push_back(node);
        // Reversed, so the first neighbour in adj ends up on top.
        for (auto it = adj[node].rbegin(); it != adj[node].rend(); ++it) {
            if (!visited[*it]) stack.push_back(*it);
        }
    }
    return order;
}

vector<vector<int>> buildGraph(int n, const vector<pair<int, int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) {                 // undirected: store both ways
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    return adj;
}

import java.util.*;

class Traversal {
    // Fewest edges from start to every node; -1 if unreachable.
    static int[] bfs(List<List<Integer>> adj, int start) {
        int[] dist = new int[adj.size()];
        Arrays.fill(dist, -1);
        dist[start] = 0;
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int nxt : adj.get(node)) {
                if (dist[nxt] != -1) continue;
                dist[nxt] = dist[node] + 1;
                queue.add(nxt);                     // mark when enqueued, not later
            }
        }
        return dist;
    }

    // Nodes in the order a depth-first search first reaches them.
    static List<Integer> dfs(List<List<Integer>> adj, int start) {
        boolean[] visited = new boolean[adj.size()];
        List<Integer> order = new ArrayList<>();
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (visited[node]) continue;
            visited[node] = true;
            order.add(node);
            // Reversed, so the first neighbour in adj ends up on top.
            List<Integer> nbrs = adj.get(node);
            for (int i = nbrs.size() - 1; i >= 0; i--) {
                if (!visited[nbrs.get(i)]) stack.push(nbrs.get(i));
            }
        }
        return order;
    }

    static List<List<Integer>> buildGraph(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {                     // undirected: store both ways
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        return adj;
    }
}

Neighbours are tried in the order the edges were given, so all three versions produce exactly the same output.

Grids are graphs too. Each cell is a node and its up, down, left and right neighbours are its edges. You don’t build an adjacency list: work out the four neighbours on the fly, skip the ones outside the grid or on a wall, and keep dist or visited as a 2-D array.

Why it’s O(V + E)

Each node is explored once, thanks to dist or visited. Exploring a node scans its adjacency list, and the lists together hold 2E entries, because each undirected edge appears in both endpoints’ lists. Every enqueue or push comes from one of those entries (plus the start), so the frontier work is O(E) too. Both searches do O(V + E) work.

The adjacency list itself is O(V + E). On an R × C grid, V = R·C and E is at most 2·R·C, so both are O(R·C).

Common mistakes

node = queue.popleft(); seen.add(node)    # ✗ node may already be queued twice
seen.add(nxt); queue.append(nxt)          # ✓ mark as you enqueue

node = queue.pop(0)        # ✗ O(n) per pop
node = queue.popleft()     # ✓ deque: O(1)

Variations

• Multi-source BFS. Put all starting points in the queue at distance 0 before the loop. Each node then gets its distance to the nearest source, in one O(V + E) pass: distance to the nearest exit, or minutes until every orange has rotted.
• 0-1 BFS. When each edge costs 0 or 1, use a deque: push the neighbour to the front for a 0 edge and to the back for a 1 edge. It gives Dijkstra’s answers in O(V + E).
• BFS on a grid. Queue (row, col) pairs, keep dist as a 2-D array, and loop over four direction offsets. If moves depend on more than position (keys held, walls you may still break), put that in the state: (row, col, keys) is one node.
• Recursive DFS. A few lines shorter, and handy when you need work after the children finish (subtree sizes, cycle detection with three colours, topological order by finishing time). It’s fine when depth is small; otherwise raise the limit with care or use a stack.
• Connected components. Loop over every node, and start a new DFS (or BFS) from each one that isn’t visited yet. The number of starts is the number of components, and labelling nodes with the start’s number tells you which component each is in.