bfs/
lib.rs

1//! Breadth-First Search (BFS) on a graph.
2//!
3//! BFS visits neighbours of the current node before going deeper. It is
4//! typically used to compute shortest paths on unweighted graphs, to
5//! find connected components, or to perform level-order traversal.
6//!
7//! This module exposes BFS as two helpers operating on an adjacency list:
8//!
9//! * [`bfs_distances`] — returns the shortest distance (in edges) from a
10//!   source vertex to every reachable vertex. Unreachable vertices are
11//!   absent from the result.
12//! * [`bfs_order`] — returns the vertices in the order they are
13//!   dequeued (i.e., the BFS visitation order).
14//!
15//! The graph is passed as `&[Vec<usize>]`, indexed by vertex. Vertex ids
16//! are `0..n` where `n = graph.len()`.
17
18use std::collections::{HashMap, VecDeque};
19
20/// Compute the shortest distance (in number of edges) from `source` to
21/// every vertex reachable from it.
22///
23/// Returns a map from vertex id to distance. Vertices that are not
24/// reachable from `source` are absent. `source` itself maps to `0`.
25///
26/// # Panics
27///
28/// Panics if `source >= graph.len()`.
29pub fn bfs_distances(graph: &[Vec<usize>], source: usize) -> HashMap<usize, usize> {
30    assert!(source < graph.len(), "source vertex out of range");
31    let mut dist: HashMap<usize, usize> = HashMap::new();
32    let mut queue: VecDeque<usize> = VecDeque::new();
33    dist.insert(source, 0);
34    queue.push_back(source);
35    while let Some(v) = queue.pop_front() {
36        let d = dist[&v];
37        for &u in &graph[v] {
38            if !dist.contains_key(&u) {
39                dist.insert(u, d + 1);
40                queue.push_back(u);
41            }
42        }
43    }
44    dist
45}
46
47/// Return the visitation order of BFS starting from `source`.
48///
49/// The first element is always `source`. Each subsequent element is the
50/// next vertex dequeued from the BFS queue.
51///
52/// # Panics
53///
54/// Panics if `source >= graph.len()`.
55pub fn bfs_order(graph: &[Vec<usize>], source: usize) -> Vec<usize> {
56    assert!(source < graph.len(), "source vertex out of range");
57    let mut visited = vec![false; graph.len()];
58    let mut order = Vec::with_capacity(graph.len());
59    let mut queue: VecDeque<usize> = VecDeque::new();
60    visited[source] = true;
61    queue.push_back(source);
62    while let Some(v) = queue.pop_front() {
63        order.push(v);
64        for &u in &graph[v] {
65            if !visited[u] {
66                visited[u] = true;
67                queue.push_back(u);
68            }
69        }
70    }
71    order
72}
bfs/lib.rs

bfs/
lib.rs
