algorithms_edu/algo/graph/
dfs.rs

1pub mod iterative {
2    //! An implementation of iterative DFS with an adjacency list
3    //!
4    //! - Time Complexity: O(V + E)
5    //!
6    //! # Resources
7    //!
8    //! - [W. Fiset's video](https://www.youtube.com/watch?v=7fujbpJ0LB4&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=4)
9
10    use crate::algo::graph::{Edge, WeightedAdjacencyList};
11
12    impl WeightedAdjacencyList {
13        /// Perform a depth first search on a graph with n nodes
14        /// from a starting point to count the number of nodes
15        /// in a given component.
16        ///
17        /// In this particular implementation we just increment a counter each time we
18        /// visit a new node. This, by itself, is not of much use, but you'll soon see that
19        /// many other advanced algorithms are based on this DFS prototype.
20        pub fn dfs(&self, start: usize) -> usize {
21            let mut count = 0;
22            let mut visited = vec![false; self.node_count()];
23            let mut stack = Vec::new();
24
25            // start by visiting the start node
26            stack.push(start);
27            visited[start] = true;
28
29            while let Some(node) = stack.pop() {
30                count += 1;
31                let neighbours = &self[node];
32                for &Edge { to, weight: _ } in neighbours {
33                    if !visited[to] {
34                        stack.push(to);
35                        visited[to] = true;
36                    }
37                }
38            }
39
40            count
41        }
42    }
43
44    #[cfg(test)]
45    mod tests {
46        use super::*;
47        #[test]
48        fn test_dfs_iterative() {
49            // Create a fully connected graph
50            //           (0)
51            //           / \
52            //        5 /   \ 4
53            //         /     \
54            // 10     <   -2  >
55            //   +->(2)<------(1)      (4)
56            //   +--- \       /
57            //         \     /
58            //        1 \   / 6
59            //           > <
60            //           (3)
61            let graph = WeightedAdjacencyList::new_directed(
62                5,
63                &[
64                    (0, 1, 4.),
65                    (0, 2, 5.),
66                    (1, 2, -2.),
67                    (1, 3, 6.),
68                    (2, 3, 1.),
69                    (2, 2, 10.), // Self loop
70                ],
71            );
72
73            let count = graph.dfs(0);
74            assert_eq!(count, 4);
75            println!("DFS node count starting at node 0: {}", count);
76
77            let count = graph.dfs(4);
78            assert_eq!(count, 1);
79            println!("DFS node count starting at node 4: {}", count);
80        }
81    }
82}
83pub mod recursive {
84    //! An implementation of recursive DFS with an adjacency list
85    //!
86    //! - Time Complexity: O(V + E)
87    //!
88    //! # Resources
89    //!
90    //! - [W. Fiset's video](https://www.youtube.com/watch?v=7fujbpJ0LB4&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=4)
91
92    use crate::algo::graph::UnweightedAdjacencyList;
93
94    impl UnweightedAdjacencyList {
95        pub fn dfs_recursive(&self, start: usize) -> usize {
96            fn _dfs(
97                graph: &UnweightedAdjacencyList,
98                node: usize,
99                visited: &mut [bool],
100                count: &mut usize,
101            ) {
102                *count += 1;
103                visited[node] = true;
104                for &neighbour in &graph[node] {
105                    if !visited[neighbour] {
106                        _dfs(graph, neighbour, visited, count);
107                    }
108                }
109            }
110            let mut count = 0;
111            // let visited = vec![false; self.len()];
112            _dfs(self, start, &mut vec![false; self.node_count()], &mut count);
113            count
114        }
115    }
116
117    #[cfg(test)]
118    mod tests {
119        use super::*;
120        #[test]
121        fn test_dfs_recursive() {
122            // Create a fully connected graph
123            //           (0)
124            //           / \
125            //          /   \
126            //         /     \
127            //        <       >
128            //   +->(2)<------(1)      (4)
129            //   +--- \       /
130            //         \     /
131            //          \   /
132            //           > <
133            //           (3)
134            const N: usize = 5;
135            let mut graph = UnweightedAdjacencyList::with_size(N);
136            graph.add_directed_edge(0, 1);
137            graph.add_directed_edge(0, 2);
138            graph.add_directed_edge(1, 2);
139            graph.add_directed_edge(1, 3);
140            graph.add_directed_edge(2, 3);
141            graph.add_directed_edge(2, 2); // Self loop
142
143            let count = graph.dfs_recursive(0);
144            assert_eq!(count, 4);
145            println!("DFS node count starting at node 0: {}", count);
146
147            let count = graph.dfs_recursive(4);
148            assert_eq!(count, 1);
149            println!("DFS node count starting at node 4: {}", count);
150        }
151    }
152}
algorithms_edu/algo/graph/dfs.rs

algorithms_edu/algo/graph/
dfs.rs
