haar_lib/graph/
kruskal.rs

1//! 最小全域木 (Kruskal)
2
3use crate::{ds::unionfind::UnionFind, graph::*};
4
5/// Kruskal法
6///
7/// グラフが連結ならばSomeに包んで最小全域木の辺集合を返す。
8/// 非連結ならばNoneを返す。
9///
10/// **Time complexity** $O(E \log E)$
11pub fn kruskal<E: EdgeTrait>(g: &Graph<Undirected, E>) -> Option<Vec<&E>>
12where
13    E::Weight: Ord + Copy,
14{
15    let n = g.len();
16    let mut edges = g
17        .nodes_iter()
18        .flat_map(|v| &v.edges)
19        .map(|e| (e, e.weight()))
20        .collect::<Vec<_>>();
21    edges.sort_unstable_by_key(|&(_, c)| c);
22
23    let mut uf = UnionFind::new(n);
24    let mut ret = vec![];
25
26    for (e, _) in edges {
27        let (u, v) = (e.from(), e.to());
28        if !uf.is_same(u, v) {
29            uf.merge(u, v);
30            ret.push(e);
31        }
32    }
33
34    (ret.len() == n - 1).then_some(ret)
35}
36
37#[cfg(test)]
38mod tests {
39    use super::*;
40
41    #[test]
42    fn test() {
43        let mut g = Graph::<Undirected, _>::new(6);
44        g.extend(
45            vec![
46                (0, 1, 1),
47                (0, 2, 3),
48                (1, 2, 1),
49                (1, 3, 7),
50                (2, 4, 1),
51                (1, 4, 3),
52                (3, 4, 1),
53                (3, 5, 1),
54                (4, 5, 6),
55            ]
56            .into_iter()
57            .map(|(u, v, w)| Edge::new(u, v, w, ())),
58        );
59
60        let ans = kruskal(&g).unwrap().iter().map(|e| e.weight).sum::<i32>();
61
62        assert_eq!(ans, 5);
63    }
64}
haar_lib/graph/kruskal.rs

haar_lib/graph/
kruskal.rs
