世界科技研究与发展WORLDSCI2TECHR&D第30卷第6期Vol.30No.62008年12月751-753页Dec.2008pp.751-753冗余拓扑图简易遍历算法的研究与应用3邵明基上官右黎摘要:简单图遍历算法已经非常成熟,但是还没有完善的冗余拓扑图遍历算法。本文提出了一种简易的冗余拓扑图遍历算法。它基于简单图的遍历算法,将带有冗余链路的拓扑图转化为不带冗余链路的简单拓扑图进行遍历。通过在计算机网络虚拟实验系统中的应用,证明了此算法的可行性和正确性。关键词:遍历算法;冗余拓扑图;虚拟实验;网络协议中图分类号:TP312文献标识码:ATheResearchandApplicationofSimpleTraversingAlgorithminRedundantTopology3SHAOMingjiSHANGGUANYouli(NetworkEducationInstituteofBeijingUniversityofPostsandTelecommunications,Beijing100088)Abstract:Thetraversingalgorithmforthesimplegraphhasbeenresearchedformanyyearsandlotsofmaturealgorithmsaredeveloped.Butthereisfewefficientalgorithmforredundanttopologygraphwhichisvaluablebecauseofitspracticalapplication.Thispaperpresentsanoveltraversingalgorithmforredundanttopologygraph.Thisalgorithmisderivedfromthetraversingalgorithmforsimplegraph,andtransformstheredundanttopologygraphintothesimplegraph.Thefeasibilityand1引言图[1](Graph)是一种复杂的数据结构,它比线性结构和树型结构复杂的最主要原因是图中的任意两个节点之间都可能存在关系。因此,对图的研究,特别是对图的遍历算法[1]的研究一直是学术界研究的焦点之一。目前,关于简单图遍历算法的研究已经比较成熟,例如深度优先遍历算法(DFS)[1]和广度优先遍历算法(WFS)[1]等。这些算法有效地解决了简单图的遍历问题,为冗余拓扑图遍历算法的研究提供了基础。在现实生活中,多数的图都是复杂图,很多人对复杂图的遍历算法进行了研究,但是至今没有提出完善的遍历算法。本文通过对冗余拓扑图进行封装改进,然后转换成简单图,通过简单图的遍历算法进行遍历,然后对求得的结果进行拆分,就可以得到冗余拓扑图的遍历结果。最后,为了说明此算法的可行性和正确性,介绍了此算法在计算机网络虚拟实验系统中的应用。图1简单图Fig.1Thesimplegraph然后从w2出发,访问w2的一个未被访问的邻接顶点w3如此下去,直到一个所有邻接点都被访问过的顶点为止。然后回溯到尚有邻接点未被访问的顶点,重复上述过程,直到图中所有与v有路径相通的顶点都被访问过;此时,若图中还存在未被访问过的顶点,则从其中一个未被访问过的顶点出发,重复上述过程,直到图中所有顶点都被访问为止。若图的存储结构未知,从某一顶点出发的深度优先遍历图的广度优先遍历算法[1,2]的策略是在访问给定顶点v之后,先访问与v邻接的所有顶点w1、w2、、wk,然后再依次从w1、w2、、wk出发,访问它们的未被访问过的邻接顶点,重复上述操作,直到图中所有被访问过的顶点的邻接顶点都被访问为止。若此时图中还有未被访问过的顶点,则从一个未被访问过的顶点出发,重复上述过程,直到图中所有的顶点都被访问过为止。若图的存储结构未知,从某一顶点出发的广度优先遍历序列可以有多种。利用图的遍历算法可求图中任意两个顶点之间的所有路径,图的关节点,图的关键路径,有向图的强连通分量,无向图的连通分量和生成树,Aov网全部顶点的拓扑排序序列图中任意两个顶点之间的最短路径等等2简单图遍历算法简单图的深度优先遍历算法(DFS)[1]和广度优先遍历算法(WFS)[1]要求所要遍历的图形必须是简单图,即图中不允许存在冗余链路。一个无冗余链路的简单图如图1。2.1深度优先遍历算法(DFS)图的深度优先遍历算法[1,2]的策略是从给定顶点v出发,在回溯之前,沿着从v出发的一条路径尽可能深入前进。其遍历算法:从v出发,访问v的一个未被访问的邻接顶点w1,再从w1出发,访问w1的一个未被访问的邻接顶点w2,无冗余链路的简单图。对于存在冗余链路的复杂图,简单图面已经进行了介绍,在此不再详述,下面就解释一下路径的的遍历算法则无法直接使用。但是带冗余链路的复杂拓扑图在现实中广泛的存在,这样对复杂图的遍历问题就成为了必须要解决的问题。通过仔细思考分析,可以有两种方法解决复杂图...