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

use crate::algo::graph::UnweightedAdjacencyList;

pub trait DfsRecursive {
    fn dfs(&self, start: usize) -> usize;
}

impl DfsRecursive for UnweightedAdjacencyList {
    fn dfs(&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.vertices_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(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);
    }
}