基于超立方体Qn节点编码的最小生成树算法

陈荷花

(太原学院,山西 太原 030024)

0 引言

树是图论中的一个基础概念，它是所有图中极为重要的一种，其中包含着图中所有的节点，而权值和又最小的树就称为这个图的最小生成树，它是带权无向连通图的极小连通子图.最小生成树的理论和算法在信息的并行传输、安全分发，以及通信网络构建、高速路铺设、配电网重构等领域发挥着重要的作用.

2015年Costas Panagiotakisa，和Georgios Tziritas关于微聚集问题(microaggregation)提出了一个HTEP算法(the hierarchical tree equi-partition algorithm)，应用于由数据定义图表网络，解决了在MST搜索空间的多元微聚集问题[1].M.Singh and L.C.Lau研究了最小生成树有界度问题[2]，在成本最优的情况下提出的一种多项式算法.P.Tewarie等人研究了最小生成树在脑网络分析中的应用[3]，Jianshe Wu等人研究了最小生成树在社区检测中的应用[4]，Xiebin Chen在折叠超立方体中给出了构建最佳独立生成树算法[5].薛瑞等人针对赋权连通图，提出了当图中存在权值相同的多条边时，求解最小生成树的改进算法[6].

生成树算法尽管已经比较普遍，各位学者研究的角度各不相同，目前还找不到基于超立方体Qn节点编码的算法.本文针对Qn的拓扑结构，基于其节点编码的特点，利用避圈法，依据广度优先的策略，给出了Qn中一种新的寻找最小生成树的算法.这一算法为超立方体中找最小生成树打开了新的视野，也为Qn中设计相应的路由算法提供了强有力的理论支撑.

1 预备知识

给定一网络图G=(V，E，w),V是非空顶点集，E是边集，w是每条边的权.一个n维超立方体互连网络Qn是一个简单无向连通图，由2n个节点和n2n-1条边构成(详细定义参见文献1).由于文中研究内容是在Qn中每条边的权值相等时进行的，因此图中权参数w将不影响最小生成树的构成，于是我们记Qn=(V，E),其中V是Qn顶点集，E是Qn中不与V相交的边集.

图1是一个4维超立方体互连网络Q4的拓扑结构，有24=16个节点和4×24-1=32条边，从0000～1111是Q4中各个节点的编码.

两个恒等的图可以用同一个图形来表示，但不恒等的图也可能具有实质上相同的图形，即两图同构(用符号≅来表示).当图G≅G′,顶点s，t∈V(G),顶点s′，t′∈V(G′),且s′与s对应，t′与t对应，如果图G中顶点s到t有路，那么图G′中顶点s′到t′也一定有路，不仅长度相同，而且唯一对应[10].一棵树是一连通的无圈图，当图G中相关的路连成树T时，图G′中必有一棵与之唯一对应的树T′生成.

为了研究的方便，文中借用了超立方体的同构拓扑结构.下面图2是图1所给4维超立方体Q4的一种同构拓扑结构.

图1 4维超立方体Q4图2 4维超立方体Q4的一种同构拓扑结构

文中涉及的记号术语(下面未给出特别定义的)，请参见文献[11].

当节点s，t之间的汉明距离dH(s，t)=h时，si、ti中就会存在h个不同分量(h≤n).若Qn中两节点s，t相邻，则s，t之间的汉明距离等于1，即s，t相邻当且仅当dH(s，t)=1.

定义2在n维超立方体Qn的所有节点中，到根节点s的汉明距离等于i的点的集合记为Vi,即Vi={v·dH(s，v)=i，v∈V(Qn)}.

定理[ 11 ]若T是一棵树，则ε=v - 1(归纳法可证).即任一棵树T中，边数ε比顶点数v少一.

图3 寻找Qn中最小生成树的算法流程图

2 基于Qn节点编码的生成树算法

目前，图论中已经有很多经典算法可以构造一个图的最小生成树，如Kruskal 算法、Prim 算法.但在超立方体中基于其节点编码的最小生成树算法还未有人研究，接下来本文将利用n维超立方体Qn的同构拓扑结构，基于Qn节点编码，利用避圈法，采用广度优先策略，给出Qn中寻找最小生成树的算法.

2.1 算法思想

在一个n维超立方体Qn中，若要寻找以v0为根节点的一棵最小生成树，首先根据定义2，可以得到Qn中的n个点集V1，…，Vn.然后从v0出发，在从Vi和Vi+1(i=1，2，…，i-1)选点添边的过程中，对Vi中的每一个节点，要从其最高位开始，依次向Vi+1中的每个节点连边.连边遵循这样的规则：取x∈Vi,y∈Vi+1,则xy∈E(T),当且仅当T∪xy不含圈.最终生成的最小生成树共连2n-1条边.

2.2 算法框图

本算法的框图见图3.

2.3 算法步骤

算法 输入：超立方体Qn,根节点v0=(00…0),T0=Φ,仅包含根节点的集合V0={v0},置：i=1，j=1，k=0.

①求Vi={v|dH(v0，v)=i，v∈V(Qn)}.

②记录V1，V2，…，Vn.

③取ui∈Vk-1，vj∈Vk.

④若dH(ui，vj)≠1,置i= ：i+1,转③；否则，进入下一步.

⑤若Tk∪uivj含圈,置i= ：i+1,转③；否则，进入下一步.

⑥记录Tk,置Tk= ：Tk∪uivj.

⑨若k

⑩输出Tn,结束算法.

2.4 算法复杂度分析

算法质量的优劣会影响程序效率的高低，该算法完成一次总共需要执行10步.在算法的执行过程中，步骤①需要计算2n-1次，步骤④和⑤最多会各循环n次，而且每循环一次另需判断n次，即这里共计算了n2+2n次，步骤⑦、⑧和⑨最多会各循环n次，于是又计算了n3次，这样，该算法在最坏的情况下完成一次，总共会执行2n-1+n3+n2+2n次运算，因此该算法的时间复杂度为O(2n),其中n代表Qn中的节点数.

3 实例验证

例 请在超立方体Q3和Q4中各找出一棵最小生成树.

解 这里采用超立方体Q3和Q4的同构拓扑结构，利用新提出的算法，找到了超立方体Q3和Q4中各自存在的一棵最小生成树，见下图4、图5.

图4 超立方体Q3中的一棵最小生成树图5 超立方体Q4中的一棵最小生成树

4 结束语

超立方体互连网络之所以长期受到各层次研究者们的喜爱，是因为它自身许多独特的优良性质吸引着大家.本文利用n维超立方体的正则性和高度对称性，基于Qn节点编码的特点，在Qn的同构拓扑结构中，找到了一种新的最小生成树算法，这为Qn中设计相应路由算法提供了依据，为超立方体互连网络的并行广播路由算法打开了新的视角.但该算法的不足之处是它的时间复杂度为O(2n),不够理想，有待进一步优化.