图的连通性快速算法

1、图的连通性快速算法陆鸣盛1，沈成康2（1.同济大学计算机科学与工程系，上海200092 ; 2.同济大学结构工程与防灾研究所，上海200092）摘要：介绍了一种新的图的连通性算法.用指引元表和相邻点表来描述图，用支撑树生长法进行连通性广延搜.与传统算法相比，采用新算法可使时间开销.同时本算法可推广应用于各种与图的连通性文章编号：0253 - 374 X(2001 ) 04 - 0436 - 04索,其中又轮流使用二个堆栈来取用和存入本层及下一层的生长点从0（ N 2）级降到0 （ N In N ）级.并通过实例对新算法进行了验证关键词：图论；连通性；计算机算法；地震；灾害预估 中图分类号：0

2、157 . 5文献标识码：ASp eedy Algo rithm fo r Conn exit y of Grap h1 2L U M ing2sheng , S H EN Cheng2kang(1. Department of Computer Science and Engineering , Tongji U niversit y ,Shanghai 200092 ,China ;2 .In stit ute of Struct ural Engin eeri ng and Disaster Reduct ion , Tongji U niversit y ,Sha nghai 2000

3、92 ,Ch ina)Ab stra ct : Mo nte2CarIo met hod is usually adop ted to calculate p robabilities of co nnect bet ween every no de wit h so urce no de of pipe net w hen estimating disaster of t he pipe net due to eart hquake . The hardco re of t he met ho d is check2up algo rit hm of t he co nnexit y of

4、grap h . The adjoint mat rix is used as basic data st ruct ure describing t he map in t he t raditio nal algo rit hm. If N is no de number of pipe net , then t he spending of time will be O2(N ) 2level . Thus it is not tolerable fo r great net . A new algo rit hm is int roduced in t his pap er . A d

5、irect eleme nt table and a adjoin point table are used to describe t he grap h . A growt h met ho d of suppo rt t ree is int ro duced to make exte nsive search of co nn exity. There in t wostacks are used alter n ately to get t he growt h point of curre ntlayer and depo sit t he growt h point of n e

6、xt layer . Seque ntially , t he spending of time will be reduced O ( NX ln N ) 2level . The new algo rit hm is used to calculate t he p ro babilities of co nnect fo r water supply net of Puxi in Shanghai. The no de and pipeline number of t he net is 434 and 742 respectively. Simulated 100 000 times

7、, abo ut 6 minutes o nly are spent wit h Pentium 166 co mp uter . This algo rit hm may be applied in vario us p ro blems concer ned wit h t he co nnexit y check of grap h and sho uld quicken greatly calculatio n speed.Ke y wo rd s : gra p h t heory ; conn exit y ; co mp uter algo rit hm ; eart hquak

8、e ; disaster estimatio n中的输在上海市科学技术发展基金研究课题上海市煤气系统和供水系统震害预估及抗震对策研究配管网部分，要求对整个管网提出可靠性评价 1 .通常的做法是把管网抽象成一个无向图，其节点分成源点（代表水厂、水库、唧站、进水点、煤气厂、煤气储配站等）与汇点；而其每条边则对应管网中的一条管线已知每条管线的管径、管长、材质、接口方式、地质条件及其他有关震害的参数,即可算出每条管线在指定震级水平、指定状态下的有效概率.依据每条边的有效概率，算出图中各节点与源点之间的连通概率，以此作出管网可靠性总体评价.通常使用随机数模拟法（Mon te2Carlo法）来计算图的节点

9、连通概率2 ,3 .但对收稿日期:2000 - 01 - 24于较大规模的网络，由于运算时间漫长，因此常用的算法很难承受.为了节省运算时间，本文设计了一种新 的算法，使得图的连通性算法大大加速，在运算速度上获得了实质性的突破.1 Monte2Carl O 法Mon te2Carlo法用于图的可靠性总体评价比较成熟，其具体做法分为以下三步：(1)模拟每条边是否失效.对每条边产生一个0,1区间均匀分布的随机数，对照该边的有效概率，若 后者小于前者，则认为该边在本次模拟中失效 ，在网络中剔除此边；反之则保留此边.如此遍及每条边，除 去被剔除者，就可得一个本次模拟的有效子网 .(2)用图论算法对所得的

10、有效子网作连通性检查，在有效子网中可以在它与源点间找到一条通路者即认为此节点有效，否则认为此节点在本次模拟中失效.(3)大量重复步骤(1) ( 2)，得到各节点的有效频数.除以模拟次数得到各节点有效概率的模拟近似值.值得注意的是，在第(2)步检查连通性环节中，现有程序多采用邻接矩阵来描述图，计算在二维数组(矩阵的自然映照)上进行.由此，程序中的数据存储空间开销将与节点数N的平方成正比.在时间开销上，即便用了广延搜索法，它的运算次数也还是0( N 2 )级的.因此，当网络规模不大时，现有算法尚可承受.而当网络规模充分大时，用于连通性检查的运算时间将随节点数N的平方增长.而Monte2Carlo法

11、本身立足于大量重复模拟，次数常以十万、百万计.因此'，现有算法将难以承受.为了解决此问题，必须对图的2图的连通性算法的新设计为了大量压缩数据存储空间，缩短运算时间，对图的连通性检查环节，从变更图的描述的数据结构出发，对图的连通性算法进行了彻底的改写.为了直观地阐明新算法的数据结构和程序流程，图1给出了展示本算法信息流程的数据结构图解 2.1数据输入为了计算管网的可靠性,前道程序苣点嵌引的)门1厂只需向本程序输入每条边的边号(NL ),&引元我"円Iql I I边的两端节点号(L N )，以及已经确定的 艳邻点舉亡匚亡21节点#¥该边有效概率P.由于Monte

12、2Carlo模拟瑶盘边序(中|丨丨】下丁 |的需要，增设边的有效性表 (ON).需指出：输 边号边两塢节点号边有效KtSfi：曲脊敕性 人的是,NL边号表的设置是为了方便实际：更i管网原始数据整理,这样可以不必要求1边号连续,而且允许对网络中的各边进“边救L 行增删、改动等修改编辑，从而使方案论WNLLPir111p11k11kH-U4p h一h b灌虑耳NS证变得较为方便.但它并不介入网络连muz7通成的实质性计算段中存放着与该节点相 邻的所有节点的节点序.所以每一段的 长度就是那一个节点的邻接度数.指引图1新算法信息流程数据结构示意图Fig. 1 Sketch gra ph of inf

13、ormation f lo w anddate structure of new algorithm元表IP同相邻点表P2紧密相联，其中只有前N + 1个单元的值，即IP (1) , ? , IP ( N + 1)是有意义的.为 了调用的一致，预置IP第一个单元的值为 0 ,即IP (1) = 0 .以后的N个值则是P2的N段的累计长度，即 下标值.例如，第1个节点总共与其他 4个节点相邻，则IP ( 2)的值为0 + 4 = 4 ,紧跟着第2个节点与5个 节点相邻，则IP (3)的值为4 + 5 = 9 .依次类推，最后一个单元的值必定是整个图中无向边数的2倍，即IP(N + 1) = L

14、>2 .换言之，图中N个节点的相邻点依次分段连续存放于P2中，而IP则给出了对应于这些段的界限值，即P2中各段终止的下标值.见图由于P2是连续存放的，所以I段的起1P始界,就是上一段的终止界加1 ,即等于IP2所示的示意图.12J J+I|0| I丨门(I) + 1 .于是，要考察网络中与第 I个节点相邻的那些节点，则只须在P2表中第IP+lR- R I-I 2:与第】个节点 =相哪的节点与第F牛节点 相邻的节点卉+1p：rr I IT I(I) + 1到IP ( I + 1)这一区段中搜寻.这样就把通常用来描述邻接矩阵的二维数组压 稀疏矩阵压缩时就常使用这种处理方式.IP的长度为节点数

15、N + 1 ,而P2的长度则为Fig. 2图2指引元表示意图Sketch map of direct element ta ble.对于IP和P2这种数据结构组合，从节边数的二倍，这是由于在本体系中把一条无向边化成两条有向边 点集角度可便捷地查询节点间的邻接关系，而从边的角度看，P2中每一单元实际上还对应着一条有向边为了使IP - P2描述体系与输入的原始L N体系之间沟通，又设置了与P2对应的LL表.在LL表中存放|着P2中每一单元(即每一条有向边)在Li N体系中的边序.在接下来的运算中，将主要在节点指引 体系中进行，而当需要有关边的信息时，可通过LL数组间址寻访，直达边集L N体系.必须

16、指出中无论节点或边只须使用它的序，就能具体确定一个节点或一条边.这两个序在原始数据输入后自动生成，它们都是连续的.问题在于，在对具体网络进行数据编码时，有必要给节点及边赋予一个 点号与边号是人工事先指定的，它们并不要求连续.在该体系中，“序实际上是表的下标(即地址)IP - P2，在计算，由程序号”节，而边号则由NL表给出，节点号由N I表给出.它们在连通性计算时均不必出现，仅在显示中间结果或最终结果时才用到.与二维数组相比，这样做的结果不仅大大节约了存储空间，而且在今后连通性计算时为了查清某个节点I与另外哪些节点相邻，并弄清这些相邻节点上的信息，就不必在N范围里进行，而只须在P2(IP (

17、I + 1 )到P2 ( IP ( I) + 1)中去考察，也就是只须在节点I的相邻接的节点数(即连通度)范围内进行.网络节点的平均连通度G与网络中节点多少并无直接关系，G = 2 L / N.在实际计算时，G可视为一个常量.于是，在计算中，凡遇到搜寻节点邻接关系处，搜索次数从N 律退化为常量(在本例中取为3 . 5 4.0).(2) 在上述数据结构体系下，对全网络进行Monte - Carlo模拟的具体做法是：首先把对应于全部边集的 ON表全体置0 (表示无效)，然后对每条边j产生一个0,1区间的随机数 R ,对照此边有效概率P ( j)，若P( j)黒，则将ON ( j)置为1 (表示有效

18、)，否则ON ( j)仍保持为0 (无效).如此就得到了一个子网.接着对此 有效子网检查它的连通性.可按以下思路进行：从源点出发，逐层生成有效子网的支撑树，然后检查所有节 点，在支撑树上的，是与源点连通的节点；没上树的节点，则不能与源点相连通厂它们就是本次模拟中失效的 节点;若支撑树有L K层，则程序需进行L K遍扫视，显然，层数L K与网络大小规模、拓扑构架及源点的多少和在网内的分布都有关系.对于日常遇到的供水、供气网络，一般框定L K与 N成正比,还是比较相称的.(3) 在生成支撑树时，首轮生成点是源点.以后都遵循这样的规律 :这一轮新长出的支撑树上的节点 ， 就是下一轮的生长点.直到某一

19、轮已经没有新的节点上树 ，则支撑树生成完毕.判断节点上树的条件是：与 生长点相邻、该边在有效子网内且该节点未上树者 .节点上树与否的标记为与节点相对应之 F表.(4) 为了在每轮生长支撑树时，免得重新寻找生长点，又设置了一双安放生长点的堆栈(也可用队列表)，一个放本轮的生长点，另一个放本轮长出的节点即下轮的生长点，二者交替使用.大大地提高了支撑行了对比性试算.试算是在设定的管网上进行的，使用CPU为pentiun166微机，模拟次数为100万次.结果如表1所示.节点数（N ）边数（L ）新算法老算法实验1511045 min 40 s10 min 15 s实验210021212 min 15

20、s42 min 20 snew and the tra dit ional algor ithm表1新、老算法对比性试算结果Ta b. 1 Results of contrastive calculation between由表中数据可以证实算法的时间复杂性 ，老算法 是0（ N2）级，而新算法则为0 （ Nin N ）级.由此，本计算程序在速度上获得了实质性的突破 .使用新算法对 项目中所有实例进行计算.例如，本项目中规模最大的 管网是自来水沪西网络，N = 434 , L = 742 ,仍旧在CPU为Pentium166的微机上,用本程序作10万次Mo nt由于新编制的程序耗时匕高效快疼右.，在本次水煤管网震害预估及抗震对策研究中，根据实际情况对现有网络给出了数十次不同的论证方案 ，在原方案基础上增删某些源点 ，增删某些节点，增删某些边或改变其 P值，如此，对每个方案都进行了计算 ，对照分析，从中找出合情合理的评估结论 ，进而提出符合要求的对 策.另外，在本文提出的数据结构体系中，允许出现平行边.所谓平行边就是指