普里姆

普里姆(Prim)算法

（1）算法思想

通过每次添加一个新节点加入集合，直到所有点加入停止的最小生成树的算法

原理：每次连出该集合到其他所有点的最短边保证生成树的边权总和最小

1. 首先随便选一个点加入集合

2. 用该点的所有边去刷新到其他点的最短路

3. 找出最短路中最短的一条连接（且该点未被加入集合）

4. 用该点去刷新到其他点的最短路

5 重复以上操作n-1次

6 最小生成树的代价就是连接的所有边的权值之和