algorithms_edu/algo/graph/
bfs.rs

1//! # Breadth First Search
2//!
3//! - Time Complexity: O(V + E)
4//!
5//! # Resources
6//!
7//! - [W. Fiset's video](https://www.youtube.com/watch?v=oDqjPvD54Ss&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=5)
8//! - [W. Fiset's video](https://www.youtube.com/watch?v=KiCBXu4P-2Y&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=6)
9
10use crate::algo::graph::UnweightedAdjacencyList;
11use std::collections::VecDeque;
12
13impl UnweightedAdjacencyList {
14    /// Perform a breadth first search on a graph a starting node `start`.
15    pub fn bfs(&self, start: usize) -> BfsResult {
16        // Each breadth first search layer gets separated by a DEPTH_TOKEN.
17        // DEPTH_TOKENs help count the distance from one node to another because
18        // we can increment the depth counter each time a DEPTH_TOKEN is encountered
19        const DEPTH_TOKEN: usize = usize::MAX;
20        // number of nodes
21        let n = self.node_count();
22        // tracks who the parent of `i` was
23        let mut prev = vec![None; n];
24        let mut visited = vec![false; n];
25        let mut queue = VecDeque::with_capacity(n);
26
27        // Start by visiting the `start` node and push it to the queue.
28        queue.push_back(start);
29        queue.push_back(DEPTH_TOKEN);
30        visited[start] = true;
31
32        let mut depth = 0;
33
34        // Continue until the BFS is done.
35        while let Some(node) = queue.pop_front() {
36            if queue.is_empty() {
37                break;
38            }
39            if node == DEPTH_TOKEN {
40                queue.push_back(DEPTH_TOKEN);
41                depth += 1;
42                continue;
43            }
44            let neighbours = &self[node];
45
46            // Loop through all edges attached to this node. Mark nodes as visited once they`re
47            // in the queue. This will prevent having duplicate nodes in the queue and speedup the BFS.
48            for &neighbour in neighbours {
49                if !visited[neighbour] {
50                    visited[neighbour] = true;
51                    prev[neighbour] = Some(node);
52                    queue.push_back(neighbour);
53                }
54            }
55        }
56
57        BfsResult { prev, depth }
58    }
59}
60pub struct BfsResult {
61    prev: Vec<Option<usize>>,
62    pub depth: usize,
63}
64
65impl BfsResult {
66    pub fn path_to(&self, end: usize) -> Vec<usize> {
67        let mut path = Vec::new();
68        let mut at = end;
69        while let Some(prev_parent) = self.prev[at] {
70            at = prev_parent;
71            path.push(at);
72        }
73        path.reverse();
74        path
75    }
76}
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81
82    #[test]
83    fn test_bfs_adjacency_list_iterative() {
84        let graph = UnweightedAdjacencyList::new_undirected(
85            13,
86            &[
87                [0, 7],
88                [0, 9],
89                [0, 11],
90                [7, 11],
91                [7, 6],
92                [7, 3],
93                [6, 5],
94                [3, 4],
95                [2, 3],
96                [2, 12],
97                [12, 8],
98                [8, 1],
99                [1, 10],
100                [10, 9],
101                [9, 8],
102            ],
103        );
104
105        let (start, end) = (10, 5);
106        let bfs_result = graph.bfs(start);
107        let depth = bfs_result.depth;
108        assert_eq!(depth, 5);
109        let path = bfs_result.path_to(end);
110        let fmtpath = format_path(&path);
111        println!(
112            "The shortest path from {} to {} is: {}\n",
113            start, end, fmtpath
114        );
115        assert_eq!(&fmtpath, "10 -> 9 -> 0 -> 7 -> 6");
116    }
117    fn format_path(path: &Vec<usize>) -> String {
118        path.iter()
119            .map(|&x| x.to_string())
120            .collect::<Vec<_>>()
121            .join(" -> ")
122    }
123}
124
125pub mod fast_queue {
126    //! # Breadth First Search (Iterative Implementation)
127    //!
128    //! This implementation does not track the depth, and thus can make use of the faster fixed size queue.
129
130    use crate::algo::graph::UnweightedAdjacencyList;
131    use crate::data_structures::queue::Queue;
132
133    pub trait BfsReconstructPath {
134        fn bfs<T: Queue<usize>>(&self, start: usize) -> Vec<Option<usize>>;
135
136        fn reconstruct_path<T: Queue<usize>>(&self, start: usize, end: usize) -> Vec<usize> {
137            let prev = self.bfs::<T>(start);
138            let mut path = Vec::new();
139            let mut at = end;
140            while let Some(prev_parent) = prev[at] {
141                at = prev_parent;
142                path.push(at);
143            }
144            path.reverse();
145            path
146        }
147    }
148
149    impl BfsReconstructPath for UnweightedAdjacencyList {
150        /// Perform a breadth first search on a graph a starting node `start`.
151        fn bfs<T: Queue<usize>>(&self, start: usize) -> Vec<Option<usize>> {
152            // number of nodes
153            let n = self.node_count();
154            // tracks who the parent of `i` was
155            let mut prev = vec![None; n];
156            let mut visited = vec![false; n];
157            let mut queue = T::with_capacity(n);
158
159            // Start by visiting the `start` node and push it to the queue.
160            queue.push_back(start);
161            visited[start] = true;
162
163            // Continue until the BFS is donw.
164            while let Some(node) = queue.pop_front() {
165                let neighbours = &self[node];
166
167                // Loop through all edges attached to this node. Mark nodes as visited once they`re
168                // in the queue. This will prevent having duplicate nodes in the queue and speedup the BFS.
169                for &neighbour in neighbours {
170                    if !visited[neighbour] {
171                        visited[neighbour] = true;
172                        prev[neighbour] = Some(node);
173                        queue.push_back(neighbour);
174                    }
175                }
176            }
177
178            prev
179        }
180    }
181
182    #[cfg(test)]
183    mod tests {
184        use super::*;
185        use crate::data_structures::queue::FixedCapacityQueue;
186        use std::collections::VecDeque;
187        #[test]
188        fn test_bfs_adjacency_list_iterative() {
189            let graph = UnweightedAdjacencyList::new_undirected(
190                13,
191                &[
192                    [0, 7],
193                    [0, 9],
194                    [0, 11],
195                    [7, 11],
196                    [7, 6],
197                    [7, 3],
198                    [6, 5],
199                    [3, 4],
200                    [2, 3],
201                    [2, 12],
202                    [12, 8],
203                    [8, 1],
204                    [1, 10],
205                    [10, 9],
206                    [9, 8],
207                ],
208            );
209
210            let (start, end) = (10, 5);
211
212            let path = graph.reconstruct_path::<VecDeque<usize>>(start, end);
213            let fmtpath = format_path(&path);
214            println!(
215                "The shortest path from {} to {} is: {}\n",
216                start, end, fmtpath
217            );
218            assert_eq!(&fmtpath, "10 -> 9 -> 0 -> 7 -> 6");
219
220            let path = graph.reconstruct_path::<FixedCapacityQueue<usize>>(start, end);
221            let fmtpath = format_path(&path);
222            println!(
223                "The shortest path from {} to {} is: {}\n",
224                start, end, fmtpath
225            );
226            assert_eq!(&fmtpath, "10 -> 9 -> 0 -> 7 -> 6");
227        }
228        fn format_path(path: &Vec<usize>) -> String {
229            path.iter()
230                .map(|&x| x.to_string())
231                .collect::<Vec<_>>()
232                .join(" -> ")
233        }
234    }
235}
algorithms_edu/algo/graph/bfs.rs

algorithms_edu/algo/graph/
bfs.rs
