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

use crate::graph::AdjacencyList;

impl AdjacencyList {
    /// 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.
    fn dfs(&self, start: usize) -> usize {
        let mut count = 0;
        let mut visited = vec![false; self.len()];
        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 in neighbours {
                if !visited[edge.to] {
                    stack.push(edge.to);
                    visited[edge.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)
        const N: usize = 5;
        let mut graph = AdjacencyList::with_size(N);
        graph.add_directed_edge(0, 1, 4);
        graph.add_directed_edge(0, 2, 5);
        graph.add_directed_edge(1, 2, -2);
        graph.add_directed_edge(1, 3, 6);
        graph.add_directed_edge(2, 3, 1);
        graph.add_directed_edge(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);
    }
}

use crate::graph::UnweightedAdjacencyList;

impl UnweightedAdjacencyList {
    /// 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.
    fn dfs(&self, start: usize) -> usize {
        let mut count = 0;
        let mut visited = vec![false; self.len()];
        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 in neighbours {
                if !visited[edge] {
                    stack.push(edge);
                    visited[edge] = true;
                }
            }
        }

        count
    }
}