PrimPrim's algorithm
从一个顶点出发，反复选取连接当前树与树外顶点的最轻边。
- 核心约束
- 每次加入的边跨越当前树与其余顶点构成的割；按最小跨割边扩展保持最小生成树的可扩展性。
- 适用问题
- 从邻接关系逐步扩展无向加权图；稠密图可用矩阵版本避免维护堆。
- 边界与取舍
- 允许负边权；非连通图需从尚未访问的顶点重新开始。更新的是顶点到当前树的最轻连接边，不是 Dijkstra 的源点路径长度。
时间与空间#
V 为顶点数，E 为无向边数；这里是 eager Prim 的索引二叉堆实现。
- 时间复杂度
- ；矩阵版
- 辅助空间
- 索引堆版 ，不含输入图
每次选连接已选集合与未选顶点的最轻边。懒惰 Prim 可能保存 候选并耗时 。非连通图要从各连通分量继续，结果为最小生成森林。