Function prim 

pub fn prim<G, F, K>(graph: G, edge_cost: F) -> Vec<(usize, usize)>
where
    G: IntoEdgeReferences + IntoNodeIdentifiers + NodeIndexable + NodeCount + IntoEdges,
    F: FnMut(G::EdgeRef) -> K,
    K: FloatMeasure,

Prim’s algorithm for computing a minimum spanning tree of a graph.

The input graph is treated as if undirected. Using improved Prim’s algorithm with runtime O(|V|^2). The function actually returns a minimum spanning forest, i.e. a minimum spanning tree for each connected component of the graph.

Arguments

• graph: weighted undirected graph.
• edge_cost: closure that returns cost of a particular edge.

Returns

• Vec<(usize, usize)>: the vector of edges of the resulting MST, where each edge is denoted by a pair of vertex indices, index order is random.

Examples

use graphalgs::mst::prim;
use petgraph::graph::UnGraph;

let mut graph: UnGraph<(), f64> = UnGraph::new_undirected();
let n0 = graph.add_node(()); let n1 = graph.add_node(());
let n2 = graph.add_node(()); let n3 = graph.add_node(());
let n4 = graph.add_node(()); let n5 = graph.add_node(());

graph.add_edge(n0, n1, 10.0); graph.add_edge(n1, n3, 4.0);
graph.add_edge(n2, n3, -5.0); graph.add_edge(n2, n0, -2.0);
graph.add_edge(n2, n5, 6.0); graph.add_edge(n5, n4, 2.0);
graph.add_edge(n3, n4, 10.0);

assert_eq!(
    prim(&graph, |edge| *edge.weight()),
    vec![(2, 0), (3, 2), (1, 3), (5, 2), (4, 5)]
);