BFS and DFS

Breadth-First Search (BFS) and Depth-First Search (DFS) are the two fundamental $O(V + E)$ graph traversal strategies: BFS explores vertices in concentric layers of increasing edge distance using a FIFO queue (VecDeque), while DFS plunges deep along a path before backtracking using a LIFO stack (Vec or recursion).

        (0)
       /   \
     (1)   (2)      BFS Visit Order (Layer by Layer): 0 -> 1 -> 2 -> 3 -> 4
     / \            DFS Visit Order (Branch Deep):    0 -> 1 -> 3 -> 4 -> 2
   (3) (4)

Comparing BFS and DFS

Recursive DFS in Rust: Avoiding Global Mutable State

In C++ or Python, programmers often store visited or adj in global mutable variables. In Rust, you have two clean, idiomatic ways to write recursive DFS without globals:

1. Pass &adj and &mut visited (or a DfsContext struct) as parameters to an inner helper function fn dfs(u: usize, adj: &[Vec<usize>], visited: &mut [bool]).
2. Compute bottom-up tree properties (such as subtree sizes or tree diameter) by passing parent: usize to avoid revisiting the parent edge without even needing a visited array!

use std::collections::VecDeque;

/// 1. BFS Bipartite Graph Check (2-Coloring) in O(V + E) time:
pub fn is_bipartite(adj: &[Vec<usize>]) -> bool {
    let n = adj.len();
    // 0 = uncolored, 1 = Red, 2 = Blue
    let mut color = vec![0u8; n];
    let mut queue = VecDeque::new();

    for start in 0..n {
        if color[start] != 0 {
            continue;
        }
        color[start] = 1;
        queue.push_back(start);

        while let Some(u) = queue.pop_front() {
            let next_color = 3 - color[u]; // Flips 1 <-> 2
            for &v in &adj[u] {
                if color[v] == 0 {
                    color[v] = next_color;
                    queue.push_back(v);
                } else if color[v] == color[u] {
                    return false; // Odd-length cycle detected!
                }
            }
        }
    }
    true
}

/// 2. Tree DFS: Computes the number of nodes in every subtree rooted at `root`.
pub fn compute_subtree_sizes(adj: &[Vec<usize>], root: usize) -> Vec<usize> {
    let mut sizes = vec![0usize; adj.len()];

    fn dfs(u: usize, parent: usize, adj: &[Vec<usize>], sizes: &mut [usize]) -> usize {
        let mut count = 1;
        for &v in &adj[u] {
            if v != parent {
                count += dfs(v, u, adj, sizes);
            }
        }
        sizes[u] = count;
        count
    }

    dfs(root, usize::MAX, adj, &mut sizes);
    sizes
}

fn main() {
    // 4-cycle (0 - 1 - 2 - 3 - 0) is bipartite:
    let square = vec![vec![1, 3], vec![0, 2], vec![1, 3], vec![0, 2]];
    // 3-cycle (0 - 1 - 2 - 0) is NOT bipartite:
    let triangle = vec![vec![1, 2], vec![0, 2], vec![0, 1]];

    assert!(is_bipartite(&square));
    assert!(!is_bipartite(&triangle));

    // Tree: 0 connected to 1 and 2; 1 connected to 3 and 4
    let tree = vec![
        vec![1, 2],
        vec![0, 3, 4],
        vec![0],
        vec![1],
        vec![1],
    ];
    let subtree_sizes = compute_subtree_sizes(&tree, 0);
    assert_eq!(subtree_sizes, vec![5, 3, 1, 1, 1]);

    println!("Square bipartite: {}, Subtree sizes from root 0: {subtree_sizes:?}", is_bipartite(&square));
}

Square bipartite: true, Subtree sizes from root 0: [5, 3, 1, 1, 1]