最小生成树

7.4　最小生成树

由生成树的定义可知,图的生成树不是唯一的。对于网,它的所有生成树中必有一棵树的各边的权值之和最小,则称该树为最小生成树。图的最小生成树有着广泛的应用价值,例如,要在n个城市之间建立通信网络图,如何连通n个城市只需要,而且通信代价最小,采用最小生成树的概念就可以解决该问题。构造最小生成树的算法主要有普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法两种。

7.4.1　普里姆算法

普里姆算法主要思想是:选定图中任一顶点作为生成树的根,然后按照将顶点逐一连通的步骤,在图中选择边,将边和顶点添加到现有树中,直至所有顶点都包含在树中,并且树中n－1条边的权值之和最小。

对图G（V,R）按照普里姆算法创建最小生成树,为了避免在添加边的过程中构成环,增加顶点集合U和边的集合TR。集合U表示最小生成树中顶点的集合,开始时为空集。集合TR表示最小生成树中边的集合,开始为空集。任选一顶点v_i加入集合U,然后在普里姆算法中的每一步,都从所有的边{（u,v）｜v∈V－U,u∈U}中找出所有代价最小的边（u,v）,同时将v并入U,（u,v）并入集合TR,直到U＝V为止。此时,TR中必有n－1条边,则T＝（V,TR）为G的最小生成树,如图7－28所示。普里姆算法的时间复杂度为O（n×n）,它与网中边的数目无关,适合于稠密图。

为了方便在集合U和V－U之间选择权值最小的边,定义lowcost数组,数组长度为图中顶点个数。lowcost[i]用来保存i号顶点与最小生成树中所有顶点间的边的最小权值,如果顶点i已经在最小生成树中,则lowcost[i]＝0；如果顶点i和目前最小生成树中所有顶点都不连通,则lowcost[i]＝∞。此外,设置一个辅助数组closest,数组长度为图中顶点个数,closest[i]是顶点i保存在lowcost[i]中的最小权值的边的邻接点的编号。

图7－28　普里姆算法

图7－29　无向网

对于图7－29中所示无向网,用普里姆算法求最小生成树的过程如下（见表7－1）。

（1）用1～7对顶点进行编号（1－A,2－B,3－C,4－D,5－E,6－F,7－G）,顶点之间没有边用权值∞表示,从顶点A开始创建最小生成树,lowcost[1]＝0,即U＝{A}。

（2）在lowcost数组中找到权值最小的,找到顶点D,最小权值的边为（closest[4],D）,权值为5。将顶点D加入U中,即使lowcost[4]＝0,U＝{A,D}。

（3）增加D到最小生成树后,其他顶点到最小生成树的最小距离可能会发生变化,将新的最小权值更新到lowcost中。在图的邻接矩阵中顶点D对应的第4行,即为与顶点D相连的边的权值,将其更新到lowcost中,同时更新closest数组。

具体程序如下。

（4）在lowcost找权值最小的,找到顶点F,最小权值边为（closest[6],F）,将顶点F加入U中,即使lowcost[6]＝0,U＝{A,D,F}。

（5）比较与F点相连的边的权值,将其更新到lowcost中,同步更新closest数组。

（6）依此类推,添加到最小生成树各边依次为:（A,D）5,（D,F）6,（A,B）7,（B,E）7,（E,C）5,（E,G）9。

表7－1　prim算法执行过程

具体程序如下。

由代码实现可知,邻接矩阵实现的普里姆算法的时间复杂度为O（n²）,比较适合稠密图。

7.4.2　克鲁斯卡尔算法

普里姆算法是以某顶点为起点,逐步寻找依附于各顶点上最小权值的边来构建最小生成树。克鲁斯卡尔算法不用选择起点,而是在图的所有未添加到最小生成树的边中,选择权值最小的一条边,将其添加到目前最小生成树中,再判断是否产生回路,如果产生回路则放弃,如果不产生回路就将边添加到最小生成树中。然后重复这个步骤,直至选择了n－1条边。

克鲁斯卡尔算法的实现过程为:初始时,设置生成树为只含有图的所有顶点的n个连通分量,没有边。按权值的大小逐个考虑所有的边,如果将该边加入到最小生成树,能连接两个不同的连通分量,则加入；如果加入后会构成回路,则放弃。当生成树只有一个连通分量时,算法结束。图7－31所示为对图7－30的无向网进行克鲁斯卡尔算法的执行过程,具体步骤如下。

图7－30　无向网

（1）初始状态为5个连通分量。

（2）选择权值最小边（v₂,v₃）5,加入生成树,连通v₂和v₃两个连通分量。

（3）再选择下一个权值最小边（v₃,v₄）6,加入生成树,连通两个不同的连通分量。

（4）再选择下一个权值最小边（v₂,v₄）6,加入生成树,会构成回路,放弃该边。

（5）依此类推。加入到最小生成树的各边依次为:（v₂,v₃）5,（v₃,v₄）6,（v₁,v₂）10,（v₂,v₆）11,（v₄,v₅）18。

表7－2　克鲁斯卡尔算法的执行过程

若要在图的所有未加入到最小生成树的边中查找权值最小的边,则可以定义边集数组结构,将图的所有边存储在边集数组中,并按权值从小到大排序。边集数组的定义如下。

图7－31所示为按权值排序后的边集数组。

图7－31边集数组

表7－3　边集数组

若要判定将一条边加入生成树后是否会构成回路,也即判断一条边所依附的两个顶点是否在同一个连通分量上,可将最小生成树中每个连通分量看做是一棵树,采用父结点表示法,则树中每个结点都定义一个指向父结点的指针,树根作为该连通分量的标识。判定一个顶点在哪个连通分量上,可以沿着父指针找到这个顶点所在树的根,然后判定两个树的根是否相同。合并两个连通分量就是合并两棵树,将一棵树根的结点中指向父结点的指针指向另一棵树的根即可。定义parent数组,数组长度为图中结点个数,用于记录父结点的编号。Find函数的功能是用于判断边的两个顶点是否在同一棵树上。克鲁斯卡尔算法的代码如下。

由代码分析,克鲁斯卡尔算法的时间复杂度为O（elog₂e）。克鲁斯卡尔算法主要针对边操作,边数少时效率会比较高,适用于稀疏图。