Function prim 

pub fn prim<G>(graph: &G) -> Option<SpanningTree>
where
    G: Graph<Weight = f64>,

Computes a Minimum Spanning Tree using Prim’s algorithm.

Prim’s grows the MST from an arbitrary starting node, always adding the minimum-weight edge that connects the current tree to a new node. It uses a binary min-heap (lazy deletion variant) similar to Dijkstra’s algorithm.

Works on both directed and undirected graphs; for directed graphs the algorithm finds the MST of the underlying undirected graph by considering edges in both directions.

Returns

Some(SpanningTree) if the graph is connected, or None if the graph is disconnected or has no nodes.

Complexity

O((V + E) log V) with a binary heap.

Examples

use graph_core::{AdjacencyList, Graph};
use graph_spanning::prim;

let mut g: AdjacencyList<&str> = AdjacencyList::undirected();
let a = g.add_node("A");
let b = g.add_node("B");
let c = g.add_node("C");
g.add_edge(a, b, 1.0).unwrap();
g.add_edge(b, c, 3.0).unwrap();
g.add_edge(a, c, 2.0).unwrap();

let mst = prim(&g).unwrap();
assert_eq!(mst.edges.len(), 2);
assert_eq!(mst.total_weight, 3.0); // A-B(1) + A-C(2)