Function prim 

pub fn prim<T>(graph: &Graph<T, f64>) -> Vec<EdgeIndex>

Prim 算法

计算无向加权图的最小生成树 返回构成 MST 的边索引列表

复杂度

• 时间：O((V + E) log V) - 使用二叉堆
• 空间：O(V) - 距离数组和堆

示例

use god_gragh::graph::Graph;
use god_gragh::graph::traits::GraphOps;
use god_gragh::algorithms::mst::prim;

let mut graph = Graph::<&str, f64>::undirected();
let a = graph.add_node("A").unwrap();
let b = graph.add_node("B").unwrap();
let c = graph.add_node("C").unwrap();
let d = graph.add_node("D").unwrap();
graph.add_edge(a, b, 1.0).unwrap();
graph.add_edge(a, c, 4.0).unwrap();
graph.add_edge(b, c, 2.0).unwrap();
graph.add_edge(b, d, 5.0).unwrap();
graph.add_edge(c, d, 3.0).unwrap();

let mst_edges = prim(&graph);
assert_eq!(mst_edges.len(), 3); // n-1 条边