Breadth-first traversal

Lesson · 10 min read · Graphs · Traversing a graph

Visit everything one step away, then two, then three: a queue gives the order, and the first visit to a node is along a shortest path.

In rings

Breadth-first search explores outwards from the start in rings: first every node one edge away, then every node two edges away, and so on. Where depth-first search commits to one branch, breadth-first search advances on every branch at once, one step at a time.

Every node labelled with its distance from 0. Breadth-first search visits the d=1 ring before any node at d=2.

That order has a consequence worth more than the traversal itself: the first time the search reaches a node, it has done so by a path with the fewest possible edges. Breadth-first search is the shortest-path algorithm for unweighted graphs, and a whole pattern module later is built on it.

The algorithm

A first-in, first-out queue produces the rings automatically. Nodes at distance d are all in the queue before any node at distance d + 1 is added, because those are only added when a node at distance d is taken out.

Breadth-first traversal

bfs(s)

Add s to visited and to the back of an empty queue.
While the queue is not empty: take u from the front.
For each neighbour v of u not in visited: add v to visited and to the back of the queue.

traverse(graph)

For each node s: if s is not in visited, call bfs(s).

Mark when you enqueue

The one detail that separates a correct breadth-first search from a slow one is when a node is marked visited. Mark it when it joins the queue, not when it leaves.

t was queued from a. When b is processed, t is already marked, so it is not queued a second time.

If marking waited until a node was dequeued, t would be queued once from a and again from b. On a grid, where most cells have two or more neighbours already in the queue, that multiplies the work several times over and can turn an accepted solution into a timeout.

Step by step

The same seven-node graph as the depth-first lesson. Compare the orders: depth-first went 0, 1, 3, 2, 4; breadth-first goes 0, 1, 2, 3, 4, because 2 is one step from 0 while 3 is two.

Breadth-first traversal from node 0. The label d is the distance at which each node was found.

Step 1 / 9

queue (front → back)
00
visit order
—0
Mark 0 visited and put it in the queue.
Step 2 / 9

queue (front → back)
1021
visit order
00
Take 0 from the front of the queue. Its unvisited neighbours 1, 2 are marked now and joined the back of the queue.
Step 3 / 9

queue (front → back)
2031
visit order
0011
Take 1 from the front of the queue. Its unvisited neighbours 3 are marked now and joined the back of the queue.
Step 4 / 9

queue (front → back)
30
visit order
001122
Take 2 from the front of the queue. It has no unvisited neighbours.
Step 5 / 9

queue (front → back)
40
visit order
00112233
Take 3 from the front of the queue. Its unvisited neighbours 4 are marked now and joined the back of the queue.
Step 6 / 9

queue (front → back)
empty0
visit order
0011223344
Take 4 from the front of the queue. It has no unvisited neighbours.
Step 7 / 9

queue (front → back)
50
visit order
0011223344
The queue is empty but 5 is unvisited: start again from 5.
Step 8 / 9

queue (front → back)
60
visit order
001122334455
Take 5 from the front of the queue. Its unvisited neighbours 6 are marked now and joined the back of the queue.
Step 9 / 9

queue (front → back)
empty0
visit order
00112233445566
Take 6 from the front of the queue. It has no unvisited neighbours. The queue is empty and every node is visited. Order: 0, 1, 2, 3, 4, 5, 6.

just taken from the queuewaiting in the queueprocessededge that first reached a node

Implementation

Use a real queue: collections.deque in Python, ArrayDeque in Java, VecDeque in Rust. Removing from the front of a Python list or a JavaScript array costs O(n) and quietly makes the traversal quadratic; the JavaScript version below uses an array with a moving head index instead.

from collections import deque

def bfs_order(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    for nb in adj:
        nb.sort()
    seen = [False] * n
    order = []
    for s in range(n):
        if seen[s]:
            continue
        seen[s] = True
        q = deque([s])
        while q:
            u = q.popleft()
            order.append(u)
            for v in adj[u]:
                if not seen[v]:
                    seen[v] = True      # mark on enqueue, so v is queued once
                    q.append(v)
    return order

#include <algorithm>
#include <queue>
#include <vector>

std::vector<int> solve(int n, const std::vector<std::vector<int>>& edges) {
    std::vector<std::vector<int>> adj(n);
    for (const auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    for (auto& nb : adj) std::sort(nb.begin(), nb.end());
    std::vector<bool> seen(n, false);
    std::vector<int> order;
    for (int s = 0; s < n; ++s) {
        if (seen[s]) continue;
        seen[s] = true;
        std::queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            order.push_back(u);
            for (int v : adj[u])
                if (!seen[v]) { seen[v] = true; q.push(v); }   // mark on enqueue
        }
    }
    return order;
}

import java.util.*;

class Solution {
    public int[] bfsOrder(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) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        for (List<Integer> nb : adj) Collections.sort(nb);
        boolean[] seen = new boolean[n];
        int[] order = new int[n];
        int count = 0;
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int s = 0; s < n; s++) {
            if (seen[s]) continue;
            seen[s] = true;
            q.add(s);
            while (!q.isEmpty()) {
                int u = q.poll();
                order[count++] = u;
                for (int v : adj.get(u))
                    if (!seen[v]) { seen[v] = true; q.add(v); }   // mark on enqueue
            }
        }
        return order;
    }
}

function bfsOrder(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
  for (const nb of adj) nb.sort((a, b) => a - b);
  const seen = new Array(n).fill(false);
  const order = [];
  const q = new Array(n);
  let head = 0, tail = 0;            // an array used as a queue: O(1) at both ends
  for (let s = 0; s < n; s++) {
    if (seen[s]) continue;
    seen[s] = true;
    q[tail++] = s;
    while (head < tail) {
      const u = q[head++];
      order.push(u);
      for (const v of adj[u]) {
        if (!seen[v]) { seen[v] = true; q[tail++] = v; }   // mark on enqueue
      }
    }
  }
  return order;
}

use std::collections::VecDeque;

fn solve(n: i64, edges: &[[i64; 2]]) -> Vec<i64> {
    let n = n as usize;
    let mut adj = vec![Vec::new(); n];
    for e in edges {
        let (u, v) = (e[0] as usize, e[1] as usize);
        adj[u].push(v);
        adj[v].push(u);
    }
    for nb in adj.iter_mut() {
        nb.sort();
    }
    let mut seen = vec![false; n];
    let mut order = Vec::with_capacity(n);
    let mut q = VecDeque::new();
    for s in 0..n {
        if seen[s] {
            continue;
        }
        seen[s] = true;
        q.push_back(s);
        while let Some(u) = q.pop_front() {
            order.push(u as i64);
            for &v in &adj[u] {
                if !seen[v] {
                    seen[v] = true;                     // mark on enqueue
                    q.push_back(v);
                }
            }
        }
    }
    order
}

import Data.List (foldl', sort)
import qualified Data.Map.Strict as M
import qualified Data.Set as S
import Data.Sequence (Seq (..), (|>))
import qualified Data.Sequence as Q

solve :: Int -> [[Int]] -> [Int]
solve n edges = reverse (snd (foldl' start (S.empty, []) [0 .. n - 1]))
  where
    adj = M.map sort (M.fromListWith (++) (concat [[(u, [v]), (v, [u])] | [u, v] <- edges]))
    start acc@(seen, order) s
      | S.member s seen = acc
      | otherwise = bfs (Q.singleton s) (S.insert s seen) order
    -- the queue is a Data.Sequence: O(1) at both ends
    bfs Empty seen order = (seen, order)
    bfs (u :<| rest) seen order =
      let fresh = [v | v <- M.findWithDefault [] u adj, not (S.member v seen)]
          seen' = foldl' (flip S.insert) seen fresh          -- mark on enqueue
      in bfs (foldl' (|>) rest fresh) seen' (u : order)

The same code is the reference solution to Breadth-first order of a graph, where it is compiled and run against the tests in all six languages.

Two variations come up constantly. To work level by level, take the queue's length at the start of each round and process exactly that many nodes: those are the current ring. To recover a shortest path, store for each node the node it was discovered from, then follow those links back from the target.

parent = {s: None}
q = deque([s])
while q:
    u = q.popleft()
    for v in adj[u]:
        if v not in parent:
            parent[v] = u          # parent doubles as the visited set
            q.append(v)
path = []
while t is not None:               # walk back from the target
    path.append(t)
    t = parent.get(t)
path.reverse()                     # only valid if the target was reached

std::unordered_map<int, int> parent{{s, -1}};
std::deque<int> q{s};
while (!q.empty()) {
    int u = q.front();
    q.pop_front();
    for (int v : adj[u])
        if (!parent.count(v)) {
            parent[v] = u;                  // parent doubles as the visited set
            q.push_back(v);
        }
}
std::vector<int> path;
for (int x = t; x != -1;) {               // walk back from the target
    path.push_back(x);
    auto it = parent.find(x);
    x = it == parent.end() ? -1 : it->second;
}
std::reverse(path.begin(), path.end());   // only valid if the target was reached

Map<Integer, Integer> parent = new HashMap<>();
parent.put(s, null);
Deque<Integer> q = new ArrayDeque<>(List.of(s));
while (!q.isEmpty()) {
    int u = q.poll();
    for (int v : adj.get(u))
        if (!parent.containsKey(v)) {
            parent.put(v, u);               // parent doubles as the visited set
            q.add(v);
        }
}
List<Integer> path = new ArrayList<>();
for (Integer x = t; x != null; x = parent.get(x))   // walk back from the target
    path.add(x);
Collections.reverse(path);                // only valid if the target was reached

const parent = new Map([[s, null]]);
const q = [s];
for (let head = 0; head < q.length; head++) {
    const u = q[head];
    for (const v of adj[u])
        if (!parent.has(v)) {
            parent.set(v, u);               // parent doubles as the visited set
            q.push(v);
        }
}
const path = [];
for (let x = t; x !== null && x !== undefined; x = parent.get(x))   // walk back from the target
    path.push(x);
path.reverse();                           // only valid if the target was reached

let mut parent: HashMap<usize, Option<usize>> = HashMap::from([(s, None)]);
let mut q = VecDeque::from([s]);
while let Some(u) = q.pop_front() {
    for &v in &adj[u] {
        if !parent.contains_key(&v) {
            parent.insert(v, Some(u));      // parent doubles as the visited set
            q.push_back(v);
        }
    }
}
let mut path = Vec::new();
let mut x = Some(t);
while let Some(node) = x {                // walk back from the target
    path.push(node);
    x = parent.get(&node).copied().flatten();
}
path.reverse();                           // only valid if the target was reached

bfsPath :: Array Int [Int] -> Int -> Int -> [Int]
bfsPath adj s t = reverse (walk t)        -- only valid if the target was reached
  where
    parent = go (Map.singleton s Nothing) (Seq.singleton s)   -- parent doubles as the visited set
    go par q = case Seq.viewl q of
      Seq.EmptyL -> par
      u Seq.:< rest ->
        let new = [ v | v <- adj ! u, not (Map.member v par) ]
            par' = foldl (\m v -> Map.insert v (Just u) m) par new
        in go par' (foldl (Seq.|>) rest new)
    walk x = x : maybe [] walk (Map.findWithDefault Nothing x parent)   -- walk back from the target

Complexity, and which search to use

TimeO(n + m)

SpaceO(n)

Every node enters the queue once and every edge is examined once from each end. The queue can hold a whole ring at once: on a star, n − 1 nodes.

	Depth-first	Breadth-first
Structure	call stack or explicit stack	queue
Order	one branch to the end, then back up	ring by ring from the start
Shortest path, unweighted	no	yes: the first visit is along a shortest path
Natural for	cycles, components, topological order, enumerating paths	fewest steps, levels, nearest target
Extra memory	depth of the search	width of the widest ring

When either will do, as in counting components, pick the one you can write without a bug. When the question says "fewest", "minimum number of moves" or "nearest", it is breadth-first.