Graph Traversal with Vec and VecDeque

Representing a graph as a contiguous adjacency list (Vec<Vec<usize>>) and traversing it with Vec (stack) or VecDeque (double-ended queue) powers $O(V + E)$ linear-time graph algorithms including Kahn's topological sort, cycle detection, and 0-1 BFS on binary-weighted graphs.

0-1 BFS on a Graph with Edge Weights in {0, 1} (`VecDeque`):
  Current Vertex `u` at distance `d`:
    |-- Edge (u -> v) has weight `0` ---> `deque.push_front((v, d))`     (Explore immediately!)
    +-- Edge (u -> v) has weight `1` ---> `deque.push_back((v, d + 1))`  (Explore in next layer!)
  Runs in O(V + E) time (faster than Dijkstra's O((V + E) log V))!

1. Kahn's Algorithm for Topological Sorting & Cycle Detection ($O(V + E)$)

On a Directed Acyclic Graph (DAG) (such as a package dependency graph or build task graph), a topological sort orders all vertices so that for every directed edge $u \to v$, vertex $u$ appears before vertex $v$.

Kahn's algorithm computes the in-degree of every vertex, seeds a VecDeque with all vertices of in_degree == 0, and repeatedly pops a vertex while decrementing the in-degrees of its outgoing neighbors. If the resulting order contains fewer than $V$ vertices, the graph contains a directed cycle!

use std::collections::VecDeque;

/// Returns `Ok(topological_order)` if the directed graph is a DAG,
/// or `Err(())` if the graph contains a directed cycle.
pub fn topological_sort(num_vertices: usize, edges: &[(usize, usize)]) -> Result<Vec<usize>, ()> {
    let mut adj = vec![Vec::new(); num_vertices];
    let mut in_degree = vec![0usize; num_vertices];

    for &(u, v) in edges {
        adj[u].push(v);
        in_degree[v] += 1;
    }

    let mut queue: VecDeque<usize> = (0..num_vertices)
        .filter(|&u| in_degree[u] == 0)
        .collect();

    let mut order = Vec::with_capacity(num_vertices);

    while let Some(u) = queue.pop_front() {
        order.push(u);
        for &v in &adj[u] {
            in_degree[v] -= 1;
            if in_degree[v] == 0 {
                queue.push_back(v);
            }
        }
    }

    if order.len() == num_vertices {
        Ok(order)
    } else {
        Err(()) // Cycle detected!
    }
}

2. 0-1 BFS Using VecDeque::push_front and push_back ($O(V + E)$)

When every edge weight in a graph is either 0 or 1 (for example, navigating a grid where moving along arrows costs 0 and flipping an arrow costs 1), VecDeque solves shortest paths in $O(V + E)$ time without a BinaryHeap:

• Relaxing an edge of weight 0 pushes the neighbor to the front of the deque (push_front).
• Relaxing an edge of weight 1 pushes the neighbor to the back of the deque (push_back).

pub fn bfs_zero_one(adj: &[Vec<(usize, u8)>], start: usize) -> Vec<u32> {
    let mut dist = vec![u32::MAX; adj.len()];
    let mut deque = VecDeque::new();

    dist[start] = 0;
    deque.push_front(start);

    while let Some(u) = deque.pop_front() {
        let d = dist[u];
        for &(v, weight) in &adj[u] {
            let next_d = d + u32::from(weight);
            if next_d < dist[v] {
                dist[v] = next_d;
                if weight == 0 {
                    deque.push_front(v);
                } else {
                    deque.push_back(v);
                }
            }
        }
    }

    dist
}

fn main() {
    // 1. Topological sort of a 4-stage build graph: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3
    let dag_edges = [(0, 1), (0, 2), (1, 3), (2, 3)];
    let order = topological_sort(4, &dag_edges).unwrap();
    assert_eq!(order, vec![0, 1, 2, 3]);

    // Cyclic graph: 0 -> 1 -> 0 returns Err(())
    assert!(topological_sort(2, &[(0, 1), (1, 0)]).is_err());

    // 2. 0-1 BFS: 0 --(w=1)--> 1, 0 --(w=1)--> 2, 2 --(w=0)--> 1, 1 --(w=0)--> 3
    let adj_01 = vec![
        vec![(1, 1), (2, 1)],
        vec![(3, 0)],
        vec![(1, 0)],
        vec![],
    ];
    let dists = bfs_zero_one(&adj_01, 0);
    assert_eq!(dists, vec![0, 1, 1, 1]);

    println!("Topological order: {order:?}, 0-1 BFS distances: {dists:?}");
}

Topological order: [0, 1, 2, 3], 0-1 BFS distances: [0, 1, 1, 1]