BFS and DFS

Deep dive

How it works

In: directed graph in CSR (offsets + targets), a source (BFS) or every vertex (DFS) · Out: hop distance per vertex (BFS); postorder or a back-edge witness (DFS) · State: none between calls; per call dist and a frontier (BFS), colours and a stack (DFS) · Cost: O(V + E) time, O(V) extra memory

1. BFS (level-synchronous): dist[s] = 0 and frontier = {s}.
2. For each u in the frontier, for each neighbour v with dist[v] = ∞: set dist[v] = d + 1 and append v to the next frontier. Mark v when it is pushed, not when it is popped, so each vertex enters the queue once.
3. Swap the frontiers and repeat until the frontier is empty.
4. DFS (iterative): the stack holds (vertex, index of next edge). Look at the top: if it has an unexplored edge to a white (unvisited) vertex, color that vertex gray and push it.
5. When the top runs out of edges, color it black, append it to the postorder and pop it.
6. In a directed graph, an edge to a gray vertex is a back edge, which means a cycle.
7. Direction-optimizing BFS: when the frontier's out-edges exceed about 1/14 of the edges not yet explored, switch to bottom-up. Every unvisited vertex scans its in-edges for any parent in the frontier (a bitmap) and stops at the first hit. Switch back when the frontier falls below about V/24 vertices (Beamer: α = 14, β = 24).

CSR:  off = [0, 2, 3, 5, 5]      vertex u's neighbours = dst[off[u]..off[u+1]]
      dst = [1, 2, 2, 0, 3]      0→1, 0→2, 1→2, 2→0, 2→3

Code

pub struct Csr { pub off: Vec<u32>, pub dst: Vec<u32> } // u64 offsets once E > 4·10⁹

impl Csr {
    pub fn from_edges(n: usize, edges: &[(u32, u32)]) -> Csr {
        let mut off = vec![0u32; n + 1];
        for &(u, _) in edges { off[u as usize + 1] += 1; } // out-degree histogram
        for i in 0..n { off[i + 1] += off[i]; } // prefix sum
        let mut pos = off.clone();
        let mut dst = vec![0u32; edges.len()];
        for &(u, v) in edges { dst[pos[u as usize] as usize] = v; pos[u as usize] += 1; }
        Csr { off, dst }
    }
    pub fn n(&self) -> usize { self.off.len() - 1 }
    #[inline]
    pub fn nbrs(&self, u: u32) -> &[u32] {
        &self.dst[self.off[u as usize] as usize..self.off[u as usize + 1] as usize]
    }
}

/// Hop distance from s (u32::MAX = unreachable).
pub fn bfs(g: &Csr, s: u32) -> Vec<u32> {
    let mut dist = vec![u32::MAX; g.n()];
    let (mut cur, mut next) = (vec![s], Vec::new());
    dist[s as usize] = 0;
    let mut d = 0;
    while !cur.is_empty() {
        d += 1;
        for &u in &cur {
            for &v in g.nbrs(u) {
                if dist[v as usize] == u32::MAX { dist[v as usize] = d; next.push(v); } // mark on push
            }
        }
        std::mem::swap(&mut cur, &mut next);
        next.clear();
    }
    dist
}

/// Iterative DFS over all vertices of a directed graph. Ok(postorder) or Err(v) if a cycle reaches v.
pub fn dfs_postorder(g: &Csr) -> Result<Vec<u32>, u32> {
    #[derive(Clone, Copy, PartialEq)]
    enum C { White, Gray, Black }
    let mut color = vec![C::White; g.n()];
    let mut post = Vec::with_capacity(g.n());
    let mut stack: Vec<(u32, u32)> = Vec::new(); // (vertex, next edge index into dst)
    for s in 0..g.n() as u32 {
        if color[s as usize] != C::White { continue; }
        color[s as usize] = C::Gray;
        stack.push((s, g.off[s as usize]));
        while let Some(top) = stack.last_mut() {
            let (u, e) = *top;
            if e == g.off[u as usize + 1] { // all edges done: u finishes
                color[u as usize] = C::Black;
                post.push(u);
                stack.pop();
                continue;
            }
            top.1 += 1;
            let v = g.dst[e as usize];
            match color[v as usize] {
                C::White => { color[v as usize] = C::Gray; stack.push((v, g.off[v as usize])); }
                C::Gray => return Err(v), // back edge
                C::Black => {}            // forward or cross edge
            }
        }
    }
    Ok(post)
}

Reverse post to get a topological order. For undirected graphs, store each edge in both directions and skip the edge back to the parent when looking for cycles.

Complexity and constants

• Time O(V + E). Each edge is read once (twice for undirected graphs stored both ways).
• Memory: CSR 4(V + E) B plus dist 4V B. A visited bitmap (V/8 B) fits in cache far longer: 10⁸ vertices = 12.5 MB.
• Throughput: the dist[v] lookups are random, about 1 miss per edge when V × 4 B ≫ LLC. Graph500-class machines report billions of traversed edges per second (TEPS) per node with parallelism and direction optimization.
• A frontier queue holds at most V entries. A DFS stack holds up to V entries (a path graph).

Efficiency

• Cost: measured with the code above on an Apple M4 Pro, one thread, random directed graphs, best of 3: 2^20 vertices and 16.8 M edges take 81 ms (4.8 ns per edge, 208 M edges/s); 2^24 vertices and 134 M edges take 1.9 s (14 ns per edge, 71 M edges/s). Memory: CSR 4(V + E) B plus dist 4V B. Bound: memory latency of the random dist[v] reads.
• Levers:
  • CSR instead of Vec<Vec<u32>> — 1.56× at 2^20 vertices, none at 2^24 (measured) — graphs that fit in cache; beyond it cache misses dominate
  • visited bitmap instead of a dist array — 1.12× at 2^20, 1.22× at 2^24 (measured) — only reachability or level counts needed
  • direction-optimizing BFS — several times faster on low-diameter graphs (Beamer et al. 2012; Key facts) — huge frontiers
  • relabel vertices for locality — order of 1.5-3× (Implementation notes) — real graphs with structure; random graphs gain nothing
• Naive → standard → state of the art:
  • Vec<Vec<u32>> adjacency · 7.5 ns per edge at 2^20 vertices (measured)
  • CSR, level-synchronous (code above) · 4.8 ns per edge
  • CSR, bitmaps, direction-optimizing, multi-threaded · billions of traversed edges per second per node on Graph500-class machines (Graph500)

Implementation notes

• Relabel vertices for locality (BFS order, reverse Cuthill-McKee, degree-sorted). Neighbours then sit near each other in memory, which often gives 1.5-3× on real graphs.
• Parallel BFS: process the frontier in parallel. Claim vertices with a CAS on dist, or with a racy check followed by CAS. Gather each thread's next frontier locally, then concatenate.
• Bitmaps for frontiers in bottom-up steps: one bit per vertex, scanned 64 at a time.
• Bidirectional BFS for s-t queries: alternate the expansion of the smaller frontier from both ends. It explores about b^(d/2) instead of b^d vertices.
• Multi-source BFS (initial frontier = many sources) gives the distance to the nearest source in one pass. Use it for flood fills and influence maps.
• 0-1 BFS: a deque where 0-weight edges push to the front and 1-weight edges to the back. Exact shortest paths in O(V + E).

Pitfalls

• Marking visited on pop instead of push in BFS: duplicates enter the queue and memory grows to O(E).
• "Iterative DFS" that pushes all neighbours at once does not give correct finish times or postorder.
• Recursion: Rust spawned threads get 2 MiB stacks by default and the main thread usually 8 MiB. A path of 10⁶ vertices overflows.
• u32 offsets overflow beyond 4.29·10⁹ edges. Use u64 offsets with u32 vertex IDs.
• Vec<Vec<u32>> or HashMap adjacency: a separate allocation and pointer chase per vertex, typically several times slower than CSR.

Variants and alternatives

In production

Memory management: garbage-collector marking and Cheney's copying collector (Cheney 1970). Chip design: Lee-style maze routers (Lee 1961). Compilers: LLVM's depth_first and ReversePostOrderTraversal over control-flow graphs. High-performance computing: Graph500 and the GAP benchmark suite, Ligra and Galois (frameworks). Libraries: petgraph (Bfs, Dfs, Csr), Boost Graph Library, NetworkX. Build tools and package managers (dependency walks) and web crawlers.

Implementations

Sources

• T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., 2009.
• R. Tarjan, Depth-First Search and Linear Graph Algorithms, SIAM Journal on Computing, 1972. paper
• S. Beamer, K. Asanović, D. Patterson, Direction-Optimizing Breadth-First Search, SC, 2012. paper · code
• J. Shun, G. Blelloch, Ligra: A Lightweight Graph Processing Framework for Shared Memory, PPoPP, 2013. paper · code
• C. J. Cheney, A Nonrecursive List Compacting Algorithm, CACM, 1970. paper
• C. Y. Lee, An Algorithm for Path Connections and Its Applications, IRE Transactions on Electronic Computers, 1961. paper
• S. Beamer, K. Asanović, D. Patterson, The GAP Benchmark Suite, 2015. paper · code