资源描述：
《基于vc_的网络拓扑图中环的自动识别算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第23卷第4期武汉化工学院学报Vol.23No.42001年12月J.WuhanInst.Chem.Tech.Dec.2001文章编号:10044736(2001)04005803基于VC++的网络拓扑图中环的自动识别算法12王忠,韵湘(1.武汉化工学院计算机科学与工程系,湖北武汉430073;2.武汉邮电科学研究院,湖北武汉430074)摘要:论述了基于VC++网络拓扑图中环的自动识别算法,分析了环的存贮结构及识别跨过某链路的所有环算法.环的自动识别算法能大大提高应用程序的智能化程度,并成功应用于网络规划系统
2、中.关键词:网络拓扑;环;自动识别;链路中图分类号:TP391.41文献标识码:A的指针成员放在链路对象中,而不是节点对象中,0引言原因在于一个结点有多条链路,具有不确定性,无在网络拓扑中,各节点间通过链路相互连接法确定需定义的指针成员数量,而链路对象只可组成各种网络模型.一般来说可以把网络拓扑结能指向两个节点对象.类的部分成员定义如下.构分为两类基本结构,环和树.环是指链路首尾相ClassCNode:publicCObjectöö“节点”类连的链路集合,而除环结构以外的统称为树结构,{public:包括线性结
3、构和分支结构.若要对网络中的容量、CStringsName;öö节点名流量分析及获取节点间的最短路径、关键路径等CPointpt;öö在图中的显示位置信息来合理规划网络,自动识别网络的拓扑结构}就显得很有必要,而环的识别可以说是识别拓扑ClassCLink:publicCObjectöö“链路”类结构中的难点所在;由于目前的程序设计都采用{public:可视化编程,应用者不可能在人机交互过程中输CNode3fNode;öö指向第一个节点的指针入过多的环与树的信息,一般只绘制网络的外观CNode3sNode;öö
4、指向第二个节点的指针效果图,至于节点和链路构成何种基本拓扑结构,CStringfName;öö指向第一个节点的“节点名"需要程序中能自动完成,以提高应用程序的智能CStringsName;öö指向第二个节点的“节点名”化程度;加之传统的理论中对环结构的计算机识BOOLinCycle;öö该链路是否已经放在环中别方法均未加以介绍.基于上述三种原因本文介}绍一种基于VC++的网络拓扑图中环的自动识拓扑图中可能存在多个环,为了方便识别拓别算法.扑图后环的存贮,定义了一个环对象,以存贮构成环路径的各链路对象,及反映当前
5、环路径是否已1基于VC++的网络拓扑图中环构成环.环的类定义如下.的存贮结构ClassCCycle:publicCObjectöö“环的存贮结构”类根据图论的定义,环也称回路,是第一个顶点{public:和最后一个顶点相同的路径[1].为了识别拓扑中CObArrayCycleLinkArray;öö存贮环中链路的的环,首先确立相应图中各对象的存贮结构,以下指针数组为了重点说明环的识别算法,将网络拓扑结构及BOOLIsCycle;öö是否为环的标记对象模型简化为:拓扑图中的两类对象,即节点和}链路,这两种对象内部
6、只有体现两种对象关系的由于VC++支持可按需要进行动态缩放的成员.对象数组CObArray,同时根据环结构的特点,建一个节点可以通过多条链路连接各节点,而立一个二级指针三层结构来表示环的数据存贮结一条链路只可能连接两个节点,为了更好地反映构.二级指针三层结构如图1.两对象间的相互关系,将一个对象指向另一对象收稿日期:20001226作者简介:王忠(1968),男,湖北江陵人,讲师,硕士.第4期王忠等:基于VC++的网络拓扑图中环的自动识别算法59图1环的存贮结构Fig.1Thestoragestructureo
7、fring上述二级指针三层结构能有效地存贮环结的环.构,指针数组ArrayTempC是在识别过程中临时b.求环路径的开始节点(pHeadNode)和结存贮环的过渡数组,而最终存贮所有环结构需用束节点(pTailNode).在文档类定义一个CObArray类的指针数组All2c.找到以结束节点(pTailNode)为一个节点CycleArray.的所有K条链路.d.将先前的路径与K条链路分别建立新的2环的自动识别算法K条环路径,判断每条环路径是否构成环(条件环的自动识别理论基础是图论中的图的遍是新链路的另一节点p
8、Node与pHeadNode相历,其算法有两种:即深度优先遍历DFS(Depth同),若是环(pNode=pHeadNode)或者K=0(以FirstSearch)和广度优先遍历BFS(BreadthFirstpTailNode为端点不存在新分支)结束,否则分别[1,2]Search).为了便于环的识别,可以选择BFS算以K条新的环路径为当前环路径,转到b步继续法.执行.若要识别拓扑图
