prim求最小生成树

prim 算法建议在 kruskal 算法及相关证明掌握后进行学习，这里不再赘述。

前置知识

暂无

prim 的算法步骤

1. 确定一号节点为最小生成树。
2. 找到一条由已经属于最小生成树的点集连到还不属于最小生成树的点集的边，使得这条边在这类边中权值最小。
   令已经属于最小生成树的点集为 \(S\)，还不属于最小生成树的点集为 \(T\)，则可以表达为找到两个点 \(x,y\) 使得 \({\min_{x \in T,y \in S}\{z\}}\)，\(z\) 即为这条边的权值。
3. 记两点都已属于最小生成树的点集，累计这条边的权值进入答案。
4. 重复 2,3 的操作直到所有点都属于最小生成树的集合，输出累加值。

主要实现方法

prim 的实现步骤可以类比 dijkstra，很像
维护数组 \(d\)，找到一个点 \(x\)，使得 \(x \in T\)，且 \(d[x]\) 最小，那么就把 \(x\) 加入 \(S\) 中，并更新所有出边的 \(d[\ ]\) 值，直到所有点都加入了 \(S\) 集合，答案即为 \(\sum_{x=2}^{n}{d[x]}\)。

prim V.S kruskal

prim 时间复杂度 \(O(n^2)\)，堆优化后为 \(O(m log n)\)。
kruskal 时间复杂度 \(O(m log m)\)。
kruskal 更适用于稀疏图（即边数较少的图）。
prim 更适用于稠密图，其堆优化后的版本不如kruskal好写。

代码

咕了，什么时候补上再说。