7.4.2 克鲁斯卡尔算法在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课我们讨论求最小生成树的另外一个算法

克鲁斯卡尔算法

求最小生成树的另一个算法是克鲁斯卡尔的算法

先介绍一下算法过程

假设连通网N=（V，{E}），顶点集V

边集E

则令最小生成树的初始状态为

只有n个顶点而无边的非连通图T=（V，{}）

把边按代价自小到大排序，完成算法的初始化

算法过程是在边集E中选择代价最小的边

因为已经排好序，依次选择就可以了

若该边依附的顶点落在T中不连通的分量上

则将此边加入到T中

否则舍弃此边而选择下一条代价最小的边

以此类推，直到图中所有顶点

都在同一连通分量上为止

我们结合图例，看一下克鲁斯卡尔算法的执行过程

图1是连通网，假设我们已经按照边的代价

进行了排序，排序的结果如图1的表中所示

构造一个只含有n个顶点而没有边的非连通图T

图2给出了T的初始状态

此时T中每个顶点自成一个连通分量

有n个连通分量

按照算法步骤，在边排序的表中选择0号单元的边(v1,v3)

这是所有边中最小的一条

该边依附的顶点v1,v3落在T中不连通的分量上

把边(v1,v3)加入到T中，如图3所示

因为边(v1,v3)的加入

T中有两个连通分量被连接在一起

成为了一个包含顶点v1,v3的连通分量

T中连通分量的个数减少了一个，还有5个

继续挑选下一条最小代价的边

是边(v4,v6)，该边依附的顶点v4,v6落在

T中不连通的分量上，把边(v4,v6)加入到T中

如图4所示，连通分量个数又减少1个，还有4个

继续挑选出(v2,v5)，(v3,v6)加入到T中

结果如图5所示，现在图中还有2个连通分量

下一条挑选的边是(v1,v4)，观察图5可以看出

v1和v4属于同一连通分量

按照算法要求，舍弃它

继续选择下一条边(v2,v3)

v2,v3在两个不同的连通分量上

把边(v2,v3)加入T，结果如图6所示

图6中所有的顶点都在一个连通分量上，算法结束

克鲁斯卡尔算法的执行过程，还是比较容易理解的

教材上没有给出算法实现的代码

克鲁斯卡尔算法算法实现的关键问题有两个

第1个是排序

关于排序算法我们将在第10章详细讨论

第2个克鲁斯卡尔算法实现的关键问题是

选择最小代价边以后

要在T中判断该边所依附的顶点

是否属于不同的连通分量

如果属于不同的连通分量

边加入后这两个连通分量将并为一个连通分量

这个问题基于图结构实现是比较麻烦的

解决这个问题的思路是每个连通分量用一棵树来表示

结合图示，我们说明一下

初始状态的T，每个顶点自成一个连通分量

我们用双亲表示法来存储

图1中，6个顶点存在0到5号单元

双亲指针都是-1，表示他们都是树的根

总共有6棵树，每棵树描述一个连通分量

每个连通分量只有一个顶点

所有每棵树中也只有顶点这个根

图2中，边(v1,v3)加入T

成为了一个包含顶点v1,v3的连通分量

对应地，我们把v1和v3为根的这两棵树并未一棵树

办法是取其中一棵树的根为新树的根

另一棵树的根作为新根的孩子

这里取v1为新树的根

v3作为v1的孩子

孩子表示法数组中需要把v3的双亲置为0

表示v3的双亲是存储在0的v1

图3图4是T变化后

双亲表示法数组对应变化的情况

图4中我们可以看到只有2个顶点的双亲是-1

就是说现在只有2个连通分量了

从上面过程可以判断

如果利用树来描述连通分量

克鲁斯卡尔算法的第2个关键问题时间代价不高

算法的时间代价主要是在排序

排序算法的时间复杂度是O(nlogn)

这里是对边排序，如果边数是e条

克鲁斯卡尔算法的时间复杂度就是O(eloge)

前面我们介绍过普里姆算法

它的时间复杂度是O(n2)，这个n是顶点数

也就是说它的复杂度和顶点个数有关

克鲁斯卡尔算法的时间复杂度就是O(eloge)

它的时间复杂度边数有关

基于这样的特征，普里姆算法比较适合于稠密图

因为，边多对普里姆算法的时间效率没有影响

克鲁斯卡算法呢，比较适合以稀疏图

因为稀疏图边比较少

好，同学们，这节课就讲到这

下次课再见