Function rs_graph::mst::prim

pub fn prim<'a, 'b, G, W>(
    g: &'a G, 
    weights: &EdgeSlice<'a, 'b, G, W>
) -> Vec<G::Edge> where
    G: IndexGraph<'a>,
    G::Node: Hash,
    W: NumAssign + Ord + Copy, 

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

• g is the undirected graph weights the edge weights

If the graph is not connected, the returned vector only spans one component. This can easily be verifyed by checking the size of the returned vector.

Example

use rs_graph::{Net, Builder, EdgeVec};
use rs_graph::mst::prim;

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)].iter()
{
    g.add_edge(nodes[u], nodes[v]);
    weights.push(w);
}
let weights = EdgeVec::from_vec(&g, weights);

// run the algorithm
let tree = prim(&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);