competitive_library/graph/
minimum_spanning_tree_kruskal.rs

1//! Kruskal's minimum spanning tree algorithm.
2
3use crate::structure::disjoint_set_union::DisjointSetUnion;
4pub struct Edge(i64, i64, i64);
5
6pub fn kruskal(n: usize, edges: &[Edge]) -> i64 {
7    let mut edges = edges.iter().collect::<Vec<_>>();
8    edges.sort_by_key(|e| e.2);
9
10    let mut dsu = DisjointSetUnion::new(n);
11
12    let mut min_cost = 0;
13
14    for e in edges.iter() {
15        if dsu.is_same(e.0 as usize, e.1 as usize) {
16            continue;
17        }
18        dsu.unite(e.0 as usize, e.1 as usize);
19        min_cost += e.2;
20    }
21
22    min_cost
23}
24
25#[cfg(test)]
26mod tests {
27    use super::*;
28    #[test]
29    fn test_kruskal() {
30        let ans = kruskal(
31            5,
32            &[
33                Edge(0, 1, 10),
34                Edge(0, 3, 5),
35                Edge(1, 2, 1),
36                Edge(1, 3, 1000),
37                Edge(1, 4, 500),
38                Edge(2, 3, 100),
39                Edge(2, 4, 10000),
40                Edge(3, 4, 5000),
41            ],
42        );
43
44        assert_eq!(ans, 516);
45    }
46}