algorithms_edu/algo/graph/minimum_spanning_tree/
kruskal.rs

1//! Kruskal's algorithm for finding an miminum spanning forest.
2//!
3//! # Algorithm Overview
4//!
5//! - create a forest F (a set of trees), where each vertex in the graph is a separate tree
6//! - create a set S containing all the edges in the graph
7//! - while S is nonempty and F is not yet spanning:
8//!   - remove an edge with minimum weight from S
9//!   - if the removed edge connects two different trees then add it to the forest F, combining
10//!     two trees into a single tree
11//! - At the termination of the algorithm, the forest forms a minimum spanning forest of the graph.
12//!   If the graph is connected, the forest has a single component and forms a minimum spanning tree.
13
14use crate::algo::graph::WeightedAdjacencyList;
15use crate::data_structures::union_find::UnionFind;
16use ordered_float::OrderedFloat;
17
18impl WeightedAdjacencyList {
19    pub fn kruskal(&self) -> Option<(f64, WeightedAdjacencyList)> {
20        let n = self.node_count();
21        let mut edges = self.edges().collect::<Vec<_>>();
22        edges.sort_by_key(|(_f, _t, cost)| OrderedFloat(*cost));
23        let mut msf_edges = Vec::new();
24        let mut mst_cost = 0.;
25        let mut ds = UnionFind::with_size(n);
26        for (from, to, cost) in edges {
27            // if not connected i.e. adding this edge will not produce a cycle
28            if !ds.in_same_set(from, to) {
29                msf_edges.push((from, to, cost));
30                mst_cost += cost;
31                ds.union(from, to);
32            }
33        }
34        // TODO: support non-tree forest
35        if msf_edges.len() == n - 1 {
36            return Some((mst_cost, WeightedAdjacencyList::new_directed(n, &msf_edges)));
37        }
38
39        None
40    }
41}
42
43#[cfg(test)]
44mod tests {
45    use super::*;
46    #[test]
47    fn test_kruskal1() {
48        // from https://www.youtube.com/watch?v=jsmMtJpPnhU&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=30
49        // at 10:05
50        let g = WeightedAdjacencyList::new_directed(
51            8,
52            &[
53                (0, 1, 10.),
54                (0, 2, 1.),
55                (0, 3, 4.),
56                (2, 1, 3.),
57                (2, 5, 8.),
58                (2, 3, 2.),
59                (2, 0, 1.),
60                (3, 2, 2.),
61                (3, 5, 2.),
62                (3, 6, 7.),
63                (3, 0, 4.),
64                (5, 2, 8.),
65                (5, 4, 1.),
66                (5, 7, 9.),
67                (5, 6, 6.),
68                (5, 3, 2.),
69                (4, 1, 0.),
70                (4, 5, 1.),
71                (4, 7, 8.),
72                (1, 0, 10.),
73                (1, 2, 3.),
74                (1, 4, 0.),
75                (6, 3, 7.),
76                (6, 5, 6.),
77                (6, 7, 12.),
78                (7, 4, 8.),
79                (7, 5, 9.),
80                (7, 6, 12.),
81            ],
82        );
83        let (cost, mst) = g.kruskal().unwrap();
84        println!("{}", mst);
85        assert_eq!(cost, 20.);
86    }
87    #[test]
88    fn test_kruskal2() {
89        // from https://www.youtube.com/watch?v=xq3ABa-px_g&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=31
90        // at 08:31
91        let g = WeightedAdjacencyList::new_directed(
92            7,
93            &[
94                (0, 2, 0.),
95                (0, 5, 7.),
96                (0, 3, 5.),
97                (0, 1, 9.),
98                (2, 0, 0.),
99                (2, 5, 6.),
100                (3, 0, 5.),
101                (3, 1, -2.),
102                (3, 6, 3.),
103                (3, 5, 2.),
104                (1, 0, 9.),
105                (1, 3, -2.),
106                (1, 6, 4.),
107                (1, 4, 3.),
108                (5, 2, 6.),
109                (5, 0, 7.),
110                (5, 3, 2.),
111                (5, 6, 1.),
112                (6, 5, 1.),
113                (6, 3, 3.),
114                (6, 1, 4.),
115                (6, 4, 6.),
116                (4, 1, 3.),
117                (4, 6, 6.),
118            ],
119        );
120        let (cost, mst) = g.kruskal().unwrap();
121        println!("{}", mst);
122        assert_eq!(cost, 9.);
123    }
124}
algorithms_edu/algo/graph/minimum_spanning_tree/kruskal.rs

algorithms_edu/algo/graph/minimum_spanning_tree/
kruskal.rs
