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

//! 第四章：无向图算法
use std::{collections::HashSet, fs};
pub mod breadth_first_search;
pub mod connect;
pub mod cycle;
pub mod depth_first_search;
pub mod symbol_graph;
pub trait Search {
    fn marked(&self, v: usize) -> bool;
    fn count(&self) -> usize;
}
pub trait Path {
    fn has_path_to(&self, v: usize) -> bool;
    fn path_to(&self, v: usize) -> Option<Box<dyn Iterator<Item = usize>>>;
}
pub struct Graph {
    vertex_count: usize,
    edge_count: usize,
    adj: Vec<HashSet<usize>>,
}
impl Graph {
    pub fn new(vertex_count: usize) -> Self {
        assert!(vertex_count > 0);
        let mut adj = Vec::with_capacity(vertex_count);
        for _ in 0..vertex_count {
            adj.push(HashSet::new());
        }
        Graph {
            vertex_count,
            edge_count: 0,
            adj,
        }
    }
}
/// 向图中添加n条边
///
/// `g`:图
///
/// `x`:v
///
/// `y`:v对应的n个w
#[macro_export]
macro_rules! add_edge {
// $(...),+ 包围起来，就可以匹配一个或多个用逗号隔开的表达式
    ($g:ident,$x:expr, $($y:expr),+) =>(
        (
           $(
             $g.add_edge($x,$y)
            ),+
        )
    );
}
impl Graph {
    fn vertex_count(&self) -> usize {
        self.vertex_count
    }
    fn edge_count(&self) -> usize {
        self.edge_count
    }
    fn add_edge(&mut self, v: usize, w: usize) {
        self.adj[v].insert(w);
        self.adj[w].insert(v);
        self.edge_count += 1;
    }
    fn adj(&self, v: usize) -> &HashSet<usize> {
        &self.adj[v]
    }
    /// 打印dot格式的图结构
    fn print_dot(&self, path: &str) {
        let mut graph = r#"graph{
            label="graph"
             bgcolor=grey
             shape=circle
             "#
        .to_string();
        for v in 0..self.vertex_count {
            for w in self.adj(v).clone() {
                if w > v {
                    graph.push_str(&format!("{} -- {}\n", v, w));
                }
            }
        }
        graph.push('}');
        let _ = fs::write(path, graph);
    }
}