最小生成树

最小生成树算法思路

  通过每次添加一个新结点加入集合，直到所有点加入停止的最小生成树的算法，每次边出该集合到其他所有点的最短边，保证生成树的边权总和最小。

1. 随便选一个点加入集合；
2. 用该点的所有边去刷新到其他点的最短路径；
3. 找出最短路径中最短的一条连接（且该点未被加入集合）
4. 用该点去刷新到其他点的最短路径。
5. 重复以上操作n-1次。
6. 最小生成树的代价就是连接的所有边的权值之和。