Prim算法

定义

---

Prim算法

Prim算法是一种用于寻找有权无向图的最小生成树的贪心算法。核心是从一个点开始，每次选取最小的邻边。

步骤

---

对于一个无向连通图，设顶点集合为$V$，设已经加入最小生成树的顶点集合为U。

1. 选择一个点作为起始点u
2. 从t的邻边中选择权重最小的边(u, v)，满足$u\in U且v\in V-U$，将v加入U，令u=v，回到（2）。
3. 当U=V时，算法结束。

实现

---