graph_traversal/
bfs.rs

1use graph_collections::Queue;
2use graph_core::{Graph, NodeId};
3use std::collections::HashMap;
4
5/// Runs a breadth-first search from `start` and returns a map of
6/// `NodeId → shortest hop distance` from `start`.
7///
8/// The distance to `start` itself is `0`. Only nodes reachable from `start`
9/// appear in the map.
10///
11/// # Examples
12///
13/// ```
14/// use graph_core::{AdjacencyList, Graph};
15/// use graph_traversal::bfs;
16///
17/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
18/// let a = g.add_node(());
19/// let b = g.add_node(());
20/// let c = g.add_node(());
21/// g.add_edge(a, b, 1.0).unwrap();
22/// g.add_edge(b, c, 1.0).unwrap();
23///
24/// let dist = bfs(&g, a);
25/// assert_eq!(dist[&a], 0);
26/// assert_eq!(dist[&b], 1);
27/// assert_eq!(dist[&c], 2);
28/// ```
29pub fn bfs<G: Graph>(graph: &G, start: NodeId) -> HashMap<NodeId, usize> {
30    let mut queue: Queue<NodeId> = Queue::new();
31    let mut dist: HashMap<NodeId, usize> = HashMap::new();
32
33    queue.enqueue(start);
34    dist.insert(start, 0);
35
36    while let Some(node) = queue.dequeue() {
37        let d = dist[&node];
38        for (neighbour, _) in graph.neighbors(node) {
39            if let std::collections::hash_map::Entry::Vacant(e) = dist.entry(neighbour) {
40                e.insert(d + 1);
41                queue.enqueue(neighbour);
42            }
43        }
44    }
45
46    dist
47}
48
49/// BFS result containing both hop distances and the parent map for path
50/// reconstruction.
51///
52/// # Examples
53///
54/// ```
55/// use graph_core::{AdjacencyList, Graph};
56/// use graph_traversal::bfs_tree;
57///
58/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
59/// let a = g.add_node(());
60/// let b = g.add_node(());
61/// g.add_edge(a, b, 1.0).unwrap();
62///
63/// let tree = bfs_tree(&g, a);
64/// assert_eq!(tree.dist[&b], 1);
65/// assert_eq!(tree.parent[&b], a);
66/// ```
67pub struct BfsTree {
68    /// Shortest hop distance from the source to each reachable node.
69    pub dist: HashMap<NodeId, usize>,
70    /// Parent of each node in the BFS tree (source has no parent entry).
71    pub parent: HashMap<NodeId, NodeId>,
72}
73
74/// Runs BFS from `start` and returns a [`BfsTree`] with distances and parents.
75///
76/// Use [`reconstruct_path`](crate::reconstruct_path) on `tree.parent` to
77/// extract the shortest path to any reachable node.
78///
79/// # Examples
80///
81/// ```
82/// use graph_core::{AdjacencyList, Graph};
83/// use graph_traversal::{bfs_tree, reconstruct_path};
84///
85/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
86/// let a = g.add_node(());
87/// let b = g.add_node(());
88/// let c = g.add_node(());
89/// g.add_edge(a, b, 1.0).unwrap();
90/// g.add_edge(b, c, 1.0).unwrap();
91///
92/// let tree = bfs_tree(&g, a);
93/// let path = reconstruct_path(&tree.parent, a, c).unwrap();
94/// assert_eq!(path, vec![a, b, c]);
95/// ```
96pub fn bfs_tree<G: Graph>(graph: &G, start: NodeId) -> BfsTree {
97    let mut queue: Queue<NodeId> = Queue::new();
98    let mut dist: HashMap<NodeId, usize> = HashMap::new();
99    let mut parent: HashMap<NodeId, NodeId> = HashMap::new();
100
101    queue.enqueue(start);
102    dist.insert(start, 0);
103
104    while let Some(node) = queue.dequeue() {
105        let d = dist[&node];
106        for (neighbour, _) in graph.neighbors(node) {
107            if let std::collections::hash_map::Entry::Vacant(e) = dist.entry(neighbour) {
108                e.insert(d + 1);
109                parent.insert(neighbour, node);
110                queue.enqueue(neighbour);
111            }
112        }
113    }
114
115    BfsTree { dist, parent }
116}
graph_traversal/bfs.rs

graph_traversal/
bfs.rs
