最小生成树算法——Prim算法、Kruskal算法_prim算法得到的最小生成树唯一嘛?

一 最小生成树的性质

1 最小生成树不是唯一的，即最小生成树的树形不唯一。当图中的各边权值互不相等时，图的最小生成树时唯一的；若无向连通图的边数比顶点少1，即其本身时一棵树时，其最小生成树就是其本身。

2 最小生成树的边的权值之和是唯一的。

3 最小生成树的边数为顶点数减1。

二 Prim算法

1 基本思想

初始时从图中任取一个顶点加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都增1，重复以上步骤，直至图中所有的顶点都并入T，得到的T就是最小生成树。

2 例题

求下图的最小生成树（从顶点V1开始）

 从V1开始，含有顶点V1的边有{<V1，V2>，<V1,V3>,<V1,V4>}，与V1距离最近的顶点为V3，并将边<V1,V3>加入到边集合中，即：

含有顶点V1,V3相邻的边有{<V1,V2>,<V1,V4>,<V3,V2>,<V3,V4>,<V3,V6>,<V3,V5>}，距离最短的边是<V3,V6>，将其加入到边集合中，即：

含有顶点V1,V3,V6相邻的边有{<V1,V2>,<V1,V4>,<V3,V2>,<V3,V4>,<V6,V4>,<V3,V5>,<V6,V5>}，距离最短的边是<V6,V4>，将其加入到边集合中，即： 

然后，距离最短的边是<V3,V2>，将其加入到边集合中，即： 

 然后，距离最短的边是<V2,V5>，将其加入到边集合中，即： 

3 性能分析

• Prim算法的时间复杂度为；
• 该算法适用于求解边稠密的图的最小生成树。

 三 Kruskal算法

1 基本思想

初始时只有n个顶点而无边的非连通图，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在图中不同的连通分量上，则将边加入图中，否则舍弃该边，选择下一条权值最小的边。

2 例题

求下图的最小生成树（从顶点V1开始）

 权值最小的边为<V1,V3>，将其加入边集合中，即：

下一条权值最小的边为<V4,V6>，将其加入边集合中，即

 

下一条权值最小的边为<V2,V5>，将其加入边集合中，即

下一条权值最小的边为<V3,V6>，将其加入边集合中，即 

 下一条权值最小的边为<V2,V3>或<V3,V4>，因为<V3,V4>与<V4,V6>，<V3,V6>构成环，则只能将<V2,V3>加入边集合中，即 

3 性能分析

• Kruskal算法的时间复杂度为；
• 该算法适用于求解边稀疏而顶点较多的图的最小生成树。