algorithms_fourth 0.1.10

用rust实现算法4书中的算法，作为rust的学习实践
Documentation 
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

//! 有向图的可达性

use std::slice::Iter;

use super::Digraph;

/// 有向图的可达性
///
/// # 用法
///
///```
/// use algorithms_fourth::digraph::Digraph;
/// use algorithms_fourth::digraph::directed_dfs::DirectedDFS;
/// let mut g = Digraph::new(4);
/// g.add_edge(0, 1);
/// g.add_edge(0, 3);
/// let dd = DirectedDFS::new(&g, 0);
///let dd = DirectedDFS::new2(&g, [0, 1, 2].iter());
/// ```
pub struct DirectedDFS {
    marked: Vec<bool>,
}
impl DirectedDFS {
    pub fn new(g: &Digraph, s: usize) -> Self {
        let marked = vec![false; g.vertex_count];
        let mut dd = DirectedDFS { marked };
        dd.dfs(g, s);
        dd
    }
    pub fn new2(g: &Digraph, sources: Iter<usize>) -> Self {
        let marked = vec![false; g.vertex_count];
        let mut dd = DirectedDFS { marked };
        for s in sources {
            dd.dfs(g, *s);
        }
        dd
    }

    fn dfs(&mut self, g: &Digraph, s: usize) {
        self.marked[s] = true;
        for w in g.adj(s) {
            if !self.marked[*w] {
                self.dfs(g, *w);
            }
        }
    }
    pub fn marked(&self, v: usize) -> bool {
        self.marked[v]
    }
}
#[cfg(test)]
mod test {
    use crate::digraph::{directed_dfs::DirectedDFS, Digraph};

    #[test]
    fn test() {
        let mut g = Digraph::new(4);
        g.add_edge(0, 1);
        g.add_edge(0, 3);
        let dd = DirectedDFS::new(&g, 0);
        assert_eq!(dd.marked(0), true);
        assert_eq!(dd.marked(1), true);
        assert_eq!(dd.marked(2), false);
        assert_eq!(dd.marked(3), true);
        let dd = DirectedDFS::new(&g, 1);
        assert_eq!(dd.marked(0), false);
        assert_eq!(dd.marked(1), true);
        let dd = DirectedDFS::new2(&g, [0, 1, 2].iter());
        assert_eq!(dd.marked(0), true);
        assert_eq!(dd.marked(1), true);
        assert_eq!(dd.marked(2), true);
        assert_eq!(dd.marked(3), true);
    }
}