基于中位数的二分破圈法

季 飞，李建林

（南京信息职业技术学院，江苏南京 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|）。