最小生成树之Prim算法和Kruskal算法

一个连通图可能有多棵生成树，而最小生成树是一副连通加权无向图中一颗权值最小的生成树，它可以根据Prim算法和Kruskal算法得出，这两个算法分别从点和边的角度来解决。

Prim算法

1. 输入：一个加权连通图，其中顶点集合为V，边集合为E；
2. 初始化：Vn = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；
3. 重复下列操作，直到Vn = V：（在集合E中选取权值最小的边（u, v），其中u为集合Vn中的元素，而v则是V中没有加入Vn的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）； 将v加入集合Vn中，将（u, v）加入集合En中；）
4. 输出：使用集合Vn和En来描述所得到的最小生成树。

以下面这张图作为例子，表格中的Vertex、Kown、Cost、Path分别表示顶点信息、是否访问过，权值，到达路径；

Prim算法

我们随机的选择顶点0作为起点，其执行步骤为：