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