Function rs_graph::mst::kruskal

pub fn kruskal<'a, 'b, G, W>(
    g: &'a G, 
    weights: &EdgeSlice<'a, 'b, G, W>
) -> Vec<G::Edge> where
    G: IndexGraph<'a>,
    W: Ord, 

Run Kruskal's algorithm to solve the Minimum Spanning Tree problem on a graph.

• g is the undirected graph weights the edge weights

The algorithm actually solves a minimum spanning forest problem if the graph is not connected. This can easily be verified by checking the number of returned edges.

Example

use rs_graph::{Net, IndexGraph, EdgeVec, Builder};
use rs_graph::mst::kruskal;

let mut g = Net::new();
let mut weights: Vec<usize> = vec![];

let nodes = g.add_nodes(10);
for &(u,v,w) in &[(0,1,4), (0,2,1), (0,3,4),
                  (1,2,5), (1,4,9), (1,5,9), (1,7,7),
                  (2,3,3), (2,7,9),
                  (3,7,10), (3,9,18),
                  (4,5,2), (4,6,4), (4,8,6),
                  (5,6,2), (5,7,8),
                  (6,7,9), (6,8,3), (6,9,9),
                  (7,9,8),
                  (8,9,9)]
{
    g.add_edge(nodes[u], nodes[v]);
    weights.push(w);
}

// run the algorithm
let weights = EdgeVec::from_vec(&g, weights);
let tree = kruskal(&g, &weights.as_slice());

// check the results
assert_eq!(tree.len(), 9);
let mut sum = 0;
for e in tree { sum += weights[e]; }
assert_eq!(sum, 38);