季 飞,李建林
(南京信息职业技术学院,江苏南京 210023)
最小生成树(MST)是图论的一个经典问题,普遍存在于诸多领域中。对于MST算法,有两套独立的支撑理论。其一是:对于连通图上的任一割,e是其中权值最小的边,则e属于该图的最小生成树的边集。本文称之为割定理。其二是:对于连通图中的任一圈,e是其中权值最大的边,则e不属于该图的最小生成树的边集。本文称之为圈定理。
1926年,Boru˚vka首先提出最小生成树问题并给出相应的算法[1];此后,Kruskal和Prim分别于1956年和1957年提出了各自的算法[2,3]。大多数的后续研究[4-10],或者辅助以高效的排序、散列算法,或者引入高效的数据结构及操作,以提高算法的整体效率。这些研究依据的是割定理。1975年,管梅谷依据圈定理,提出了破圈法[11],并证明了其正确性:最小生成树与破圈次序无关。破圈法直观明了,但其中缺少“寻找圈”这一关键步骤的深入描述,只适合人工目测,不适合程式化处理,需要进一步完善。有关破圈法的后续研究不多,且主要表现为中文文献。文献[12]与[13]分别给出了其正确性的另外两种证明;文献[14]与[15]通过给任选的一棵生成树添加边,来寻找圈进而破圈,分别给出了两种实现方法,效率均为O(|E|×|V|),不太理想。
本文基于分治理念,设计出一种新的破圈算法,证明了割定理与圈定理的等价性,并依据圈定理证明了算法的正确性。新算法依据边的权值中位数,将图中的边一分为二,将原问题分解、演变为一个或多个规模较小的子问题,降低了边与边之间的耦合;在技术细节上,不是刻意地去寻找图中的圈,而是通过边合并操作来寻找圈。该算法的实现难度不大,在极端情况下的效率为O(|E|×log2|V|),在一般情况下的效率为O(|E|×log2(log2|V|))。
首先,我们给出一些定义和必要的说明,以方便后续内容的陈述。
定义1(无向权图):无向图定义为G=(V,E)。其中:V={v1,v2,…,vn}是有限的非空集合,v∈V代表图中的一个结点;E={e1,e2,…,em}是无序偶对的集合,e∈E代表vi∈V、vj∈V两结点之间的边,记为e=(vi,vj)=(vj,vi)。对于e∈E,若存在权值w(e),则称G为无向权图。
定义2(最小生成树):设G=(V,E),T=(V,ET)是G的一个子图。若T连通且不存在回路,则T是G的一棵生成树;在所有生成树中,边之权值总和最小者,称为G的一棵最小生成树。
定义3(中位数):对于一组数据,若将其按大小顺序排列,位于中间位置的那个元素,叫做这组数据的中位数。
说明:我们在算法中只使用“准中位数”,它是“中位数的中位数”[16],在最坏情况下,将规模为n的一组数据,分为规模介于(3n/ 10 -6)和(7n/ 10 +6)之间的两组,相应算法的效率为O(n)。本文其他地方提及的中位数,即指“准中位数”。
定义4(边合并):设G=(V,E),Gsub=(Vsub,Esub)是G的一个连通子图。边合并是这样的一组操作:将图G中所有邻接到结点vsub∈Vsub的、但不属于Esub的边,全部合并邻接到子图Gsub中的某一个结点v上;对于结点v上可能出现的“平行边组”,删除组中权值较大的边,每组只保留一条权值最小的边。
图1是边合并示例图。其中,Vsub={a,c,v,d},Esub={(a,c),(c,v),(v,d),(d,a),(d,c)};以实线表示Esub中的边,以虚线表示邻接到结点vsub∈Vsub的但不属于Esub的边;将虚线边全都合并邻接到Gsub中的一个结点v后,结点v上有两组平行边,分别保留权值17、11的边,删除权值18、16的边。从该示例可以看出,若实线边的权值小于虚线边的权值,则边合并操作具有破圈功能。
算法基于分治理念,依据边的权值中位数,将图中的边分为规模大致相同、权值一大一小的两个部分。若从图中移除所有大权值的边,则图可能不再连通,分解为多个连通子图。显然,这些子图中的边,小于那些被移除的边。依据圈定理,在这些子图上执行前述的边合并操作,即可实现破圈功能。随着递归的深入,不在最小生成树中的边不断被删除,最终余下的边构成图的最小生成树。
1.准备一个空集合F、空栈s,压原始图入栈s。
2.若栈s不为空,反复执行下述步骤:
(1)从s中弹出一个图,记为G=(V,E);
(2)若G为一棵树,则将e∈E加入集合F,转至步骤2;
(3)计算所有边的权值中位数,记为m;
(4)依据m构造集合Emin和Emax,使得Emin∪Emax=E,Emin∩Emax=φ,且w(e∈Emin)<w(e∈Emax);
(5)从G中移除Emax中的边,得到n≥1个连通的、但两两不连通的子图G1,G2,...,Gn;
(6)对于每个1≤i≤n:
(a)若Emax中的边,邻接了Gi中的两个结点,则从Emax中删除;
(b)在Gi上执行前文定义的边合并操作,合并时所选择的结点记为vi;
(c)压Gi入栈s;
(7)此时若Emax不为空,则其中的边,邻接到各个vi,构成图Gleft,压Gleft入栈s。
3.返回集合F,得到原始图的一棵最小生成树。
说明:步骤(5)中的“移除”,所操作的边并未被舍弃,仍然保留在集合Emax中;而步骤(a)中的“删除”,以及步骤(b)中执行边合并操作时的“删除”,所操作的边则被舍弃,不再保留在集合Emax中。
定理1:割定理与圈定理等价。
证明:割定理的逆否命题为:若边e不属于连通图的最小生成树的边集,则对于图上的任一割,e都不是其上权值最小的边。圈定理的逆否命题为:若边e属于连通图的最小生成树的边集,则对于图中的任一圈,e都不是其中权值最大的边。
首先,我们由圈定理,证明割定理的逆否命题。设图中有一个圈,由结点v1,v2,...,vn,v1依次两两邻接而成,边ei=(vi1,vi2)是圈中的最大边,不属于最小生成树的边集。对于图上任一割C=(V1,V2),若vi1∈V1,vi2∈V2,即ei跨接于割C,那么,圈中一定另有一条不同的边ej=(vj1,vj2)跨接于割C。由于ei为圈中的最大边,所以ei>ej不是割C上的权值最小的边。若边ei不跨接于割C,则显然不是其上权值最小的边。
其次,我们由割定理,证明圈定理的逆否命题。设图中有一个割,边e1,...,en跨接于该割,边ei是其中的最小边,属于最小生成树的边集。对于图中任一圈Q,若ei是该圈中的边,那么,割上一定另有一条不同的边ej存在于圈中。由于ei为割上的最小边,所以ei<ej不是圈Q中的权值最大的边。若边ei不是圈Q中的边,则显然不是其中的权值最大的边。
因为逆否命题与原命题等价,所以割定理与圈定理等价。
断言:设结点v是连通图G=(V,E)中的一个割点,现于v处将图G分割为两个连通图G1=(V1,E1)和G2=(V2,E2),这里V1∪V2=V、V1∩V2={v}且E1∪E2=E、E1∩E2=φ;再设T1、T2分别为G1、G2的最小生成树。则合并T1、T2即可得到G的最小生成树T。
定理2:设在连通图G上执行算法步骤(3)~(7),T1,T2,...,Tn,Tleft分别是图G1,G2,...,Gn,Gleft的最小生成树。则合并T1,T2,...,Tn,Tleft即得到图G的最小生成树T。
证明:至步骤(7),v1,v2,...,vn均演变为割点,Gleft通过这些割点连通到G1,G2,...,Gn,构成一个连通图Gend,据上述断言,合并T1,T2,...,Tn,Tleft即得Gend之最小生成树Tend。步骤(6)将图G演变为图Gend,步骤(3)~(5)使得在步骤(6)中:删除的边是圈中权值最大者,最小生成树T中的边留存于Gend中;未删除的边,若在G内是圈中权值最大者则在Gend内仍然是。可见,步骤(6)维持最小生成树不变,Tend≡T。
我们选用邻接表作为图的存储结构。在一次递归过程中,与效率相关的主要步骤是(3)~(6)。显然,步骤(3)~(5)的效率是O(|E|)。至于步骤(6),着眼每个Gi,遍历其中的结点,以检查其上先前是否连结有Emax中的边,并且将集合Emax实现为双向链表。这样,步骤(6)子循环执行的效率也是O(|E|)。因此,一次递归的效率为O(|E|)。
1.最坏情况
经分析,算法的最坏情况是指,在每次递归过程中,步骤(5)执行完成之后,图G同时展示出如下两个特征:其中一半的结点,因其上连结的边均属于集合Emax,而被全部移除,一个结点即构成一个子图;而余下的另一半结点,则通过集合Emin中的边,连通成一体,仅仅构成一个子图,记为Gmin=(Vmin,Emin)。步骤(a)或(b)中没有边被删除,集合Emax中的所有边均保留在Gleft中,进入了下层递归。
这样,最坏情况下的每次递归,将G=(V,E)分解演变为Gmin=(Vmin,Emin)和Gleft=(Vleft,Emax)两个连通图。这里,Vmin∪Vleft=V,Vmin∩Vleft={v}(v是集合Vmin中任选的一个结点)。因此,递归树为一棵满二叉树,深度为log2|V|,对于其中的任一层,边的总输入量保持为|E|不变。综上所述,算法在最坏情况下的效率为:
2.一般情况
一般情况下,集合Emin中的边,均匀地分布连结在图G的各个结点上,因而执行完步骤(5)之后,几乎没有结点的度为零。这样,步骤(5)完成后,若步骤(a)或(b)中没有边被删除,则得到的子图数量n>|V|1/2,亦即Gleft中的结点数大于|V|1/2。因为,一个图中边的数量不可能超过相应的完全图。
若n≈|V|1/2,则Gleft近似为完全图,算法的效率将趋于线性。为简洁起见,我们取子图的数量n=|V|1/2,且各个子图的规模相同,并假设步骤(a)或(b)中没有边被删除。再设递归树的深度为h,则有|V|1/2h=2,进而有h=log2(log2|V|)。因此,算法在一般情况下的效率可以估算为:
最后,通过实验,参照Kruskal和Prim两个算法验证本文的新算法。实验平台的OS是Windows 7、CPU是Intel(R)Core(TM)i3-2330M 2.20GHz,编程语言为JavaSE-1.8,开发工具是Eclipse Mars.2 Release(4.5.2)。
实验中输入的图均为随机生成,算法如下:
1.确定图G中结点的数量n、边的数量m;
2.初始化图G为一棵树,使得其中包含n个结点v1,v2,...,vn和n-1条边e1,e2,...,en-1。具体如下:
(1)将结点v1加入图G中
(2)for(i=2;i<=n;i++){
3.将其余的边添加到图G中。具体如下:
4.返回图G。
下面,我们以随机生成的图作为输入,验证本文之算法的有效性和高效性。下文及表格中的V、E、Sw、C分别表示结点数、边数、最小生成树的边权之和、基本操作次数,C:E则表示基本操作次数与边数的比值,E:V则表示边数与结点数的比值。
这里,在一组输入的各个图上,分别执行Kruskal、Prim和本文的算法,实验数据记录于表1中。可以看出,对于同一个图,三个算法输出相同的Sw。依据Sw的唯一性,可见本文的算法有效。
表1.不同算法输出的不同输入图G 的Sw
表2.(C:E)随E 变化实验记录(V=1000 保持不变)
表3.(C:E)随V 变化实验记录(E=64000 保持不变)
这里,使用了三组输入:第一组,各图的结点数保持不变,数据记录于表2中;第二组,各图的边数保持不变,数据记录于表3中;第三组,各图的边数与结点数的比值保持不变,数据记录于表4中。对于Kruskal算法,实验选用基于中位数的快速排序,记录的是排序操作开销,未计入不相交集合上的操作开销;对于Prim算法,实验引入最小二叉堆,以择取割上的最小边,记录的是堆上的操作开销。
表4.(C:E)随E 变化实验记录(E:V=2:1 保持不变)
三组实验数据显示,相对于两个经典算法,本文算法的C:E较为稳定,几乎呈现常量特征。可见,一般情况下,本文算法的效率较高。
本文基于分治法理念,设计出一种新的最小生成树算法,并给出了理论证明及实验结果。算法基于边权中位数,将图中的边一分为二,以降低边与边之间的耦合。在递归过程中,不是刻意地寻找圈,而是使用边合并操作,以删除不在最小生成树中的边。分析表明,新算法在最坏情况下的效率为O(|E|×log2|V|),与经典算法持平。然而,最坏情况是一种很少出现的极端情况:一半结点构成一个连通图,通过小权值的边连通;另一半结点也构成另一个连通图,通过大权值的边连通,两图之间只有极少量的大权值边相连。若各个结点邻接小权值边的机会均等,则新算法的效率为O(|E|×log2(log2|V|)),远高于经典算法,最后的实验验证了这一点。算法中权值中位数m的作用,类似于快速排序中的pivot,将边按权值大小分为两组。算法平均效率较高的另一个原因在于:部分大权值组中的边,在处理小权值组中的边时,被删除了。
另外,算法中可以方便地引入并行计算,由递归树同一层的各个节点,并发地进入下一层对应的子节点。最坏情况下,步骤(a)或(b)中没有边被删除,递归树各层的输入量都为|E|,但自上而下,操作的时间开销则依次为|E|,|E|/ 2,|E|/ 4,...因此,若引入并行计算,算法的执行时间为:Tconcurrent=O(|E|)。