Question

图所示是一个无向带权图,请分别按Prim算法和Kruskal算法求最小生成树.

请写出解题过程，谢谢

Answer 1

•普里姆（Prim）算法

基本思想

假设N=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是所求的最小生成树，其中U是T的顶点集，TE是T的边集。

（1）初始U={u0}(u0∈V),TE=φ；

（2）在所有u∈U,v∈V-U的边中选一条代价最小的边（u0，v0）并入集合TE，同时将v0并入U；

（3）重复（2），直到U=V为止。

此时，TE中必含有n-1条边，则T=（V，{TE}）为N的最小生成树。

克鲁斯卡尔（Kruskal）算法

基本思想

假设N=(V,E)是一个具有n个顶点的连通网，

（1）将n个顶点看成n个集合；

（2）按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；

（3）重复（2），直到所有的顶点都在同一个顶点集合内。  

注意：1.最小生成树不唯一。

2.该图从节点最小开始。