Breadth-First Search
Breadth-First Search (BFS) on a graph.
BFS visits neighbours of the current node before going deeper. It is typically used to compute shortest paths on unweighted graphs, to find connected components, or to perform level-order traversal.
The Rust crate lives at bfs/src/lib.rs; build & run it with:
$ cd bfs && cargo run
$ cd bfs && cargo test
Generated API reference for the Breadth-First Search crate. View the rendered API reference →
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}