最小生成树算法 - Kruskal算法

Published on 2016 - 06 - 20

Kruskal算法思想

Kruskal算法的基本思想是以边为主导地位,始终都是选择当前可用的最小权值的边。具体如下。

  1. 设一个有n个顶点的连通网络为G(V,E),最初先构造一个只有n个顶点,没有边的非连通图T={V,Ø},图中每个顶点自成一个连通分量。
  2. 当在E中选择一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上,则将此边加入到T中;否则,即这条边的两个顶点落在同一个连通分量上,则将此边舍去(此后永不选用这条边),重新选择一条权值最小的边。
  3. 如此重复下去,直到所有顶点在同一个连通分量上为止。

图3(a)所示的无向网,其邻接矩阵如图3(b)所示。利用克鲁斯卡尔算法构造最小生成树的过程如图3(c)所示,首先构造的是只有7个顶点,没有边的非连通图。剩下的过程如下(图3(c)中的每条边旁边的序号跟下面的序号是一致的)。

  1. 在边的集合E中选择权值最小的边,即(1,6),权值为10。
  2. 在集合E剩下的边中选择权值最小的边,即(3,4),权值为12。
  3. 在集合E剩下的边中选择权值最小的边,即(2,7),权值为14。
  4. 在集合E剩下的边中选择权值最小的边,即(2,3),权值为16。
  5. 在集合E剩下的边中选择权值最小的边,即(7,4),权值为18,但这条边的两个顶点位于同一个连通分量上,所以要舍去;继续选择一条权值最小的边,即(4,5),权值为22。
  6. 在集合E剩下的边中选择权值最小的边,即(7,5),权值为24,但这条边的两个顶点位于同一个连通分量上,所以要舍去;继续选择一条权值最小的边,即(6,5),权值为25。

至此,最小生成树构造完毕,最终构造的最小生成树如图3(d)所示,生成树的权为99。

克鲁斯卡尔算法的伪代码为:

Kruskal算法在每选择一条边加入到生成树集合T时,有两个关键步骤如下。

  1. 从E中选择当前权值最小的边(u,v),实现时可以用最小堆来存放E中所有的边;或者将所有边的信息(边的两个顶点、权值)存放到一个数组edges中,并将edges数组按边的权值从小到大进行排序,然后按先后顺序选用每条边。
  2. 选择权值最小的边后,要判断两个顶点是否属于同一个连通分量,如果是,则要舍去;如果不是,则选用,并将这两个顶点分别所在的连通分量合并成一个连通分量。在实现时可以使用并查集来判断两个顶点是否属于同一个连通分量以及将两个连通分量合并成一个连通分量。

等价类与并查集

并查集主要用来解决判断两个元素是否同属一个集合,以及把两个集合合并成一个集合的问题。

“同属一个集合”关系是一个等价关系,因为它满足等价关系(Equivalent Relation)的3个条件(或称为性质)。

  1. 自反性:如X≡X,则X≡X。(假设用“X≡Y”表示“X与Y等价”。)
  2. 对称性:如X≡Y,则Y≡X。
  3. 传递性:如X≡Y,且Y≡Z,则X≡Z。

如果X≡Y,则称X与Y是一个等价对(Equivalence)

等价类(Equivalent Class):设R是集合A上的等价关系,对任何a∈A,集合[a]R={x—x∈A,且aRx}称为元素a形成的R等价类,其中,aRx表示a与x等价。所谓元素a的等价类,通俗地讲,就是所有跟a等价的元素构成的集合。

等价类应用:设初始时有一集合S={1,2,3,4,5,6,7,8,9,10,11,12};依次读若干事先定义的等价对1≡5,4≡2,7≡11,9≡10,8≡5,7≡9,4≡6,3≡12,12≡1;现在需要根据这些等价对将集合S划分成若干个等价类。

在每次读入一个等价对后,把等价类合并起来。初始时,各个元素自成一个等价类(用{}表示一个等价类)。在每读入一个等价对后,各等价类的变化依次如下。

并查集(Union-Find Set)这个数据结构可以方便快速地实现这个问题。并查集对这个问题的处理思想是:初始时把每一个对象看作是一个单元素集合;然后依次按顺序读入等价对后,将等价对中的两个元素所在的集合合并。在此过程中将重复地使用一个搜索(Find)运算,确定一个元素在哪一个集合中。当读入一个等价对A≡B时,先检测A和B是否同属一个集合,如果是,则不用合并;如果不是,则用一个合并(Union)运算把A、B所在的集合合并,使这两个集合中的任两个元素都是等价的(依据是等价的传递性)。因此,并查集在处理时主要有搜索和合并两个运算。

为了方便并查集的描述与实现,通常把先后加入到一个集合中的元素表示成一个树结构,并用根结点的序号来代表这个集合。因此定义一个parent[n]的数组,parent[i]中存放的就是结点i所在的树中结点i父亲结点的序号。例如,如果parent[4]=5,就是说4号结点的父亲是5号结点。约定:如果结点i的父结点(即parent[i])是负数,则表示结点i就是它所在集合的根结点,因为集合中没有结点的序号是负的;并且用负的绝对值作为这个集合中所含结点个数。例如,如果parent[7]=-4,说明7号结点就是它所在集合的根结点,这个集合有4个元素。初始时,所有结点的parent值为-1,说明每个结点都是根结点(N个独立结点集合),只包含一个元素(就是自己)。

实现并查集数据结构主要有3个函数。代码如下。

接下来对Find函数和Union函数的实现过程做详细解释。

Find函数:在Find函数中如果仅仅靠一个循环来直接得到结点所属集合的根结点,那么通过多次的Union操作就会有很多结点在树的比较深层次中,再查找起来就会很费时。可以通过压缩路径来加快后续的查找速度:增加一个While循环,每次都把从结点x到集合根结点的路径上经过的结点直接设置为根结点的子女结点。虽然这增加了时间,但以后的查找会更快。如图4所示,假设从结点x=6开始压缩路径,则从结点6到根结点1的路径上有3个结点:6、10、8,压缩后,这3个结点都直接成为根结点的子女结点,如图4(b)所示。

Union函数:两个集合并时,任一方可作为另一方的子孙。怎样来处理呢?现在一般采用加权合并,把两个集合中元素个数少的根结点作为元素个数多的根结点的子女结点。这样处理有什么优势呢?直观上看,可以减少树中的深层元素的个数,减少后续查找时间。

例如,假设从1开始到n,不断合并第i个结点与第i+1个结点,采用加权合并思路的过程如图5所示(各子树根结点上方的数字为其parent[]值)。这样查找任一结点所属集合的时间复杂度几乎都是O(1)!

不用加权规则可能会得到如图6所示的结果。这就是典型的退化树(只有一个叶结点,且每个非叶结点只有一个子结点)现象,再查找起来就会很费时,例如查找结点n的根结点时复杂度为O(n)。

图7所示为用并查集实现前面的等价类应用例子时完整的查找和合并过程。

Kruskal算法实现

本节首先以图3(a)所示的无向网为例,解释Kruskal算法执行过程中并查集的初始化、路径压缩、合并等过程,如图8所示。

如图8(a)所示,并查集的初始状态为各个顶点各自构成一个连通分量,每个顶点上方的数字表示其parent[]元素值。

图8(b)所示是9条边组成的数组,并且已经按照权值从小到大排好序了,在Kruskal算法执行过程当中,从这个数组中依次选用每条边,如果某条边的两个顶点位于同一个连通分量上,则要舍去这条边。

在图8(c)中,依次选用(1,6)、(3,4)、(2,7)这3条边后,顶点1和6组成一个连通分量,顶点3和4组成一个连通分量,顶点2、7组成一个连通分量,顶点5单独构成一个连通分量。

在图8(d)中,选用边(2,3)后,要合并顶点2和顶点3分别所在的连通分量,合并的结果是顶点3成为顶点2所在子树中根结点(即顶点2)的子女。

在图8(e)中要特别注意,虽然选用边(4,7)时,因为这两个顶点位于同一个连通分量上,这条边将会被弃用。但在查找顶点4的根结点时,会压缩路径,使得从顶点4到根结点的路径上的顶点都成为根结点的子女结点,这样有利于以后的查找。

在图8(f)中,选用边(4,5)后,要将顶点5合并到顶点4所在的连通分量上,合并的结果是顶点5成为顶点4所在子树中根结点(即顶点2)的子女。

在图8(g)中,首先弃用边(5,7),再选用边(5,6),要将顶点6所在的连通分量合并到顶点5所在的连通分量上,因为前一个连通分量的顶点个数较少。

至此,Kruskal算法执行完毕,选用了n-1条边,连接n个顶点。

例1 利用Kruskal算法求图3(a)所示的无向网的最小生成树,并输出依次选择的各条边及最终求得的最小生成树的权。

假设数据输入时采用如下的格式进行输入:首先输入顶点个数n和边数m,然后输入m条边的数据。每条边的数据格式为:u v w,分别表示这条边的两个顶点及边上的权值。顶点序号从1开始计起。

分析:

在下面的代码中,首先读入边的信息,存放到数组edges中,并按权值从小到大进行排序。Kruskal函数用于实现Kruskal算法:首先初始化并查集,然后从edges数组中依次选用每条边,如果这条边的两个顶点位于同一个连通分量,则要弃用这条边;否则合并这两个顶点所在的连通分量。

代码如下:


该程序的运行示例如下:

Kruskal算法的时间复杂度分析:在例1的代码中,执行Kruskal函数前进行了一次排序操作,时间代价为log2m;在Kruskal函数中,最多需要进行m次循环,共执行2m次Find()操作,n-1次Union操作,其时间代价分别为O(2mlog2n)和O(n)。所以Kruskal算法的时间复杂度为:O(log2m+2mlog2n+n)。因此,Kruskal算法的时间复杂度主要取决于边的数目,比较适合于稀疏图。

扩展:Boruvka算法

Boruvka算法是最古老的一个MST算法,其思想类似于Kruskal算法思想。Boruvka算法可以分为两步:①对图中各顶点,将与其关联、具有最小权值的边选入MST,得到的是由MST子树构成的森林;②在图中陆续选择可以连接两颗不同子树且具有最小权值的边,将子树合并,最终构造MST。

例如,对图3(a)所示的无向连通图,与顶点1关联的、权值最小的边为边(1,6),将其选入MST,与顶点6关联的、权值最小的边也为边(1,6),这条边将顶点1和6连接成MST中的第1棵子树;按照类似的方法,得到另外两棵子树:顶点2、顶点7组成的第二棵子树,顶点3、4、5组成第3棵子树,如图9(a)所示。这是第1步。

第2步,选择边(2,3)将第2、3棵子树合并,以及选择边(5,6)再将第1棵子树合并进来,至此MST构造完毕,如图9(b)所示。

Boruvka算法在实现时也需要使用并查集。

例题解析

以下通过两道例题的分析,再详细介绍克鲁斯卡尔算法的基本思想及其实现方法。

例2 剑鱼行动(Swordfish)

题目来源:

Zhejiang University Local Contest 2002, Preliminary, ZOJ1203

题目描述:

给定平面上N个城市的位置,计算连接这N个城市所需线路长度总和的最小值。

输入描述:

输入文件中包含多个测试数据。每个测试数据的第1行为一个正整数N,0≤N≤100,代表需要连接的城市数目;接下来有N行,每行为两个实数X和Y,-10000≤X,Y≤10000,表示每个城市的X坐标和Y坐标。输入文件中最后一行为N=0,代表输入结束。

输出描述:

对输入文件中每个测试数据,计算连接所有城市所需线路长度总和的最小值。每对城市之间的线路为连接这两个城市的直线。输出格式为:第1行为"Case #n:",其中n为测试数据的序号,序号从1开始计起;第2行为"The minimal distance is: d",其中d为求得的最小值,精确到小数点后两位有效数字。每两个测试数据的输出之间输出一个空行。

分析:

在本题中,任意两个顶点之间都有边连通,权值为这两个顶点之间的距离。将所有边求出并存储到边的数组edges中后,按照Kruskal算法求解即可。

代码如下:


例3 网络(Network)

题目来源:

Northeastern Europe 2001, Northern Subregion, ZOJ1542, POJ1861

题目描述:

Andrew是某个公司的系统管理员,他计划为他的公司搭建一个新的网络。在新的网络中,有N个集线器,集线器之间可以通过网线连接。由于公司职员需要通过集线器访问整个网络,因此每个集线器必须能通过网线连接其他集线器(可以通过其他中间集线器来连接)。

由于有不同长度的网线可供选择,而且网线越短越便宜,因此Andrew所设计的方案必须确保最长的单根网线的长度在所有方案中是最小的。并不是所有集线器之间都可以直接连接,但Andrew会提供集线器之间所有可能的连接。

试帮助Andrew设计一个网络,连接所有的集线器并满足前面的条件。

输入描述:

输入文件中包含多个测试数据。每个测试数据的第1行为两个整数:N和M,N表示网络中集线器的数目,2≤N≤1000,集线器的编号从1~N;M表示集线器之间连接的数目,1≤M≤15000。接下来M行描述了M对连接的信息,每对连接的格式为:所连接的两个集线器的编号,连接这两个集线器所需网线的长度,长度为不超过106的正整数。两个集线器之间至多有一对连接;每个集线器都不能与自己连接。测试数据保证网络是连通的。

测试数据一直到文件尾。

输出描述:

对输入文件中的每个测试数据,首先输出连接方案中最长的单根网线的长度(必须使得这个值取到最小);然后输出设计方案:先输出一个整数P,代表所使用的网线数目;然后输出P对顶点,表示每根网线所连接的集线器编号,整数之间用空格或换行符隔开。

分析:

本题虽然没有直接要求求解生成树,但连接N个集线器的方案中如果有多于N-1条边,那么必然存在回路,因此可以去掉某些边,使得剩下的边及所有顶点构成一个生成树,仍然可以连接这N个集线器。另外,可以证明对于一个图的最小生成树来说,它的最大边满足在所有生成树的最大边里最小。因此本题实际上就是求最小生成树,并要求输出长度最长的边等信息。

另外,本题中集线器的序号是从1开始计起的,下面的代码不使用parent数组第0个元素,使用第1~N个元素。

代码如下:


参考文档