毕业设计论文通信网可靠度的近似评估算法设计.doc

《毕业设计论文通信网可靠度的近似评估算法设计.doc》由会员分享，可在线阅读，更多相关《毕业设计论文通信网可靠度的近似评估算法设计.doc（61页珍藏版）》请在三一办公上搜索。

1、 西南科技大学本科生毕业论文 通信网可靠度的近似评估算法设计摘要：通信网可靠度评估为网络设计人员提供可靠性设计依据，而近似评估算法能快速计算出可靠度的边界值。今天的通信网，尤其是主干网络，承担着海量数据的传输，因部件故障导致的通信中断将给用户带来巨大损失。为减少故障风险以及故障发生时带来的损失，工程人员在设计通信网时必须着重分析网络可靠性，通过反复评估可靠性来优化网络结构。这种可靠性需求在承担关键任务的专用网中表现得尤为突出，如果在设计阶段未充分考虑各种因素对网络可靠性的威胁，那么故障发生时所导致的通信中断将带来灾难性的后果。譬如，分析气象监测网络可靠性时，需要充分考虑各种灾害天气对通信设备的

2、破坏，通过采取保护措施来增强网络的抗毁能力；分析战术网可靠性时，需要全面考虑各种攻击带来的破坏，通过部署故障恢复策略来提高网络的抗攻击能力。 本文在网络可靠度精确算法的基础上，提出了一种近似评估通信网可靠度的算法：因子分解算法，用这种算法来近似计算通信网可靠度。该评估方法的算法实现简单，能快速评估出通信网的近似可靠度。关键词：通信网； 网络可靠度； 因子分解算法 西南科技大学本科生毕业论文 Approximate Evaluation Algorithm Design for Communication Network ReliabilityAbstract: The evaluation o

3、f communication network reliability provides the network designers with basis for reliability design, and the approximate evaluation algorithm can quickly calculate the margin value of the reliability. Currently, communication networks, the backbone networks in particular, are loaded with gigantic d

4、ata transmissions. Therefore, any break-off coursed by components breakdown will incur enormous losses for the users. To reduce the breakdown risks and its subsequent losses, the communication network designers must focus on analyzing network reliability and optimize the network structure through re

5、peated evaluation. This kind of reliability becomes more prominent when it comes to the specialized networks dealing with key tasks. During the designing phase, if the threats to the reliability havent been taken into full consideration, it may incur disastrous consequences in the case of communicat

6、ion break-off. For instance, when analyzing the meteorological monitor network, damages of communication equipments caused by should be taken into account; and when analyzing tactical networks, factors of various attacks should be considered, and restoring strategies should be adopted to enhance the

7、 anti-attack function.Based on the accurate algorithm for network reliability, this paper proposes an approximate evaluation algorithm-the factoring algorithm to calculate communication network reliability. This evaluation method, which is feasible and easy, can generate quick result of an approxima

8、te reliability of the communication network.Key words：Communication Network, Network Reliability, Factoring Algorithm 西南科技大学本科生毕业论文 目 录第1章 绪 论11.1 研究的背景及意义11.2 国内外研究状况21.3 本文主要研究内容2第2章 通信网可靠性的研究42.1 通信网可靠性一般理论42.1.1 可靠性的定义42.1.2 可靠性的连通性42.1.3 通信网可靠性设计52.2 通信网可靠性的研究方法分析52.2.1 网络的抗毁性52.2.2 网络的生存性62.2.

9、3 网络的有效性62.3 二端网络的离散概率模型72.4 算法比较92.4.1 解析算法92.4.2 上下界算法10第3章 通信网的存储结构设计123.1 图在程序中的表示123.2 图的定义与术语123.2.1 图的定义123.2.2 图的常用术语143.3 图的储存结构163.3.1 数组表示法163.3.2 邻接表163.4 图在程序中的表示173.4.1 点的度表示17 西南科技大学本科生毕业论文 3.4.2 邻结点的表示183.4.3 边的表示183.4.4 保存网络的图结构183.4.5 网络的储存过程193.4.6 举例说明21第4章 网络可靠度算法设计244.1 网络可靠度的近

10、似计算方法244.2 因子分解原理244.2.1 因子分解公式（因子定理）244.2.2 因子分解例子254.3 程序流程图274.4 因子分解在网络图中的具体操作284.4.1 因子分解删除边操作284.4.2 删除边操作程序的实现304.4.3 因子分解收缩边操作324.4.4 收缩边操作程序的实现344.4.5 网络可靠度的计算364.5 近似算法的实现364.6 程序调试及运行374.7 计算结果及实验结果384.8 综合比较52结 论54致 谢55参考文献56西南科技大学本科生毕业论文第1章 绪 论1.1 研究的背景及意义随着计算机技术和通信技术的迅猛发展，计算机通信网络将遍及社会生

11、活的方方面面，涉及到政府、企业、学校、通信、银行、军事等诸多领域，小到人们日常生活，大到国家安全稳定。如何实现通信网络高速、可靠、安全的运行时一个不可回避的现实问题。近几年来，我国通信网络规模日益扩大，网上所采用的技术和设备也越来越复杂，容量也更加集中，因此通信网中发生的故障对电信运营部门和社会生活所造成的影响越来越严重。同时社会生活对通信网的依赖程度也越来越高、对通信网可靠性的期望值越来越大，因此通信网网可靠性问题已经引起运营部门和用户的高度重视。在通信网的设计和实施过程中都对其可靠性进行了必要的考虑，在运行过程中队网络的维护和管理也都有相应的规定和方法，但是整个通信网运行的可靠性如何，通信

12、网可靠性的发展和变化情况如何，却没有给出明确的答案，其根本原因是缺乏综合评价通信网可靠性的指标和围绕该指标建立的科学的综合评价方法。因此，建立评价通信网可靠性的综合指标和评价方法具有十分重要的意义，它有助于我们对通信网的可靠性进行全面的认识，也有助于发现问题并采取有效的措施提高通信网的可靠性。无论是从满足社会需求还是从运营者自身利益出发都具有一定的实际经济价值和现实意义。通信是现代信息社会生产力必不可少的要素和衡量综合国力的重要标志，是信息社会的命脉。通信网络是现代社会需要和现代通信技术不断发展的必然结果，它不但为各种信息、多种媒体的共享提供了有效手段，同时也提高了通信质量。然而，同现代社会中

13、其他大型复杂系统一样，通信网络规模庞大，行为复杂，这对通信网分析、设计带来了巨大困难。尤其是通信网络的结构、功能、规模各有不同，导致对网络进行描述和分析的极大困难，其可靠性易受网络设备、网络管理、网络拓扑等的影响，致使通信网的可靠性难以确定。由于人们越来越关心网络正常工作的能力。所以，通信网的可靠性研究具有重要意义。1.2 国内外研究状况通信网可靠性的研究始于60年代，并由于DARPA对ARPANET的投入而得到真正的关注和发展。到目前为止，无论在通信网可靠性指标的研究还是在通信网行为建模和行为测度的评估方面都取得了大量成果。目前可靠性研究主要是针对设备冗余度、网络连通性、网络生存性等方面进行

14、讨论，涉及到的理论有概率论、图论、运筹学和相应的通信理论等。对于运行中的通信网，网管是提高其可靠性的重要手段。提高网管水平，对网络实行真正实时、动态的管理是提高可靠性的有效措施。国外的通信网可靠性研究开始较早，主要集中在网络拓扑结构的连通性上，研究的是任意两点和特定两点之间通信的可能性，以及能够进行通信的节点对的数量。我国在网络可靠性计算方面的研究较为深入，国内许多大学和科研机构的众多学者做了大量工作，取得了丰硕的成果。如有些学者在对网络全终端可靠性的上下界限的计算问题进行了较为深入的研究和探索，提出了基于断集的可靠性界的计算方法和节点失效下全端可靠性的上下界的计算公式。1.3 本文主要研究内

15、容本文的研究课题是“通信网可靠度的近似评估算法设计”本文主要是以计算机通信主干网络为对象来开展研究工作的。主要研究内容包括如下几个方面:（1）通信网可靠性分析模型本文针对计算机通信网络规模不断增长的现实，对通信主干网络的扩充问题进行了细致的研究，建立了基于全终端可靠度的网络扩充问题的数学模型，给出了求解该网络模型可靠性的算法设计。（2）网络可靠度近似计算方法尽管缺乏有效的大规模网络可靠度计算方法，但是可通过计算一些边界值来近似网络的可靠度精确值，本文就是通过找到通信网可靠度的上下界来近似测算研究。（3）网络结构在计算机内的高效存储网络好比一个个的图，有支点和树干构成，现实中网络有各种拓扑结构，

16、常见的有星形、总线形、环形和网状形等。随机图是指由网络拓扑结构转化来的一个图G=(N, E)，N是图中点的集合，E是图中边的集合,实际中点好比通信终端，边好比通信线路。根据特定的模型实现网络图在计算机中的存储。 （4）算法分析与设计通过和传统方式比较分析，确定一种新型的算法：因子分解算法，来实现对网络可靠度近似度的高效计算。第2章 通信网可靠性的研究2.1 通信网可靠性一般理论2.1.1 可靠性的定义产品的可靠性曾被定义为“产品在给定条件下和规定时间内完成规定功能的能力。”类似的可将通信网可靠性定义为：“在人为或自然的破坏作用下，通信网在规定条件下和规定时间内的生存能力。”这里最重要的是通信网

17、的规定功能和生存能力指的是什么。从图论来看，通信网是由节点和链路组成的，当任何原因造成某些节点或者链路失效时，首先会使全网的连通性变差；其次，由于连通性变差会导致网络余存部分的性能指标下降。因此，通信网的生存或规定功能应从连通性和性能指标两方而考虑。常用的判据为以下五种: 网络中给定的节点对之间至少存在一条路径；网络中一个指定节点能与一组节点能与一组节点相互通信；网路中可以相互连通的节点数大于某一阈值；网路中任意两个节点间传输时延小于某一阈值；网络的吞吐量超过某一阈值。其中前三条是从通信网的连通性考虑的，后三天是从网络的性能指标考虑的。2.1.2 可靠性的连通性这里研究通信网的可靠性主要是基于

18、网络拓扑结构，探讨当某些节点或链路失效时，网络能继续进行通信的能力。通常是根据图论中的连通性来研究的。连通性越好，可靠性越高。下而先用图论定义两个参数和是图的连通度，它是使图成为不连通图至少需要去掉的节点数。是图的结合度，它是使图成为不连通图至少需要去掉的边数。对n个点，m条变的连通图，可证明下式成立： 称为网的抗毁性，又称网的冗余度。要求图的连通性好或通信网的可靠性高，常希望F大一些，因为点数一定时，边数越多，任意两点之间的路径越多，边数最小的连通图是树。此时m=n-1，。即树中任意两点之间只有一条路径，去掉任意一条边或任意一点，必然使图变为不连通图。2.1.3 通信网可靠性设计通信网的可靠

19、性设计是要在满足给定的可靠性指标的条件下，寻找最经济的网络结构。由于影响通信网的可靠性的因素很多，在进行网的可靠性设计时，可以从构成网络部件的可靠性、网络的拓扑结构、路由选择方式等方而来考虑。网络部件的可靠性。通信网是由基本的部件或子系统等构成的，提高网的可靠性必须首先尽量降低部件或子系统的故障率。如在进行系统设计时，避免过多部件的串接，对可靠性高的系统采用备份形成并接系统等。网络的拓扑结构。要想提高通信网的可靠性，从网络拓扑结构来讲即提高连通性，至少应保证任何两个节点之间有两条无共边的路径。这是因为在实际中，端局一般维护力量较集中，可靠性较高，传输链路则是薄弱环节，由于近代技术的发展，传输链

20、路的可靠度也不会太低，一旦出现故障，也能及时修复，在修复期间另一条边出故障的概率较小，所以只要任意两节点之间有两条无共边的路径即可满足一定的可靠性。2.2 通信网可靠性的研究方法分析2.2.1 网络的抗毁性网络的抗毁性（Invulnerability）描述了通信网在人为破灯，作用下的网络可靠性，它假定“破坏者具有关于网络结构的n部资料，并采用一种确定的破坏策略”。对于一个通信网，网络的抗毁性指出至少需要破坏几个节点或几条链路才能中断部分节点之间的通信，即指出破坏一个通信网的困难程度。网络的抗毁性通过两个可靠性的确定测度粘聚度和连通度来表示。网络的抗毁性所采用的通信网生存判据为:网络中任何一对节

21、点之间至少存在一条路径。即仅考虑了网络的连通性。但对于通信来说，如果一对节点之间幸存的这条路径很长（中继节点很多)，致使信息传输时延达到不可容忍的程度，这条路径也就没有多大意义了，此时可以认为这对节点不连通。 网络的抗毁性是从图论的概念中提出来的，它从网络连通性的角度描述了网络拓扑结构对通信网可靠性的影响。对于军用通信网来说，网络的抗毁性无疑是一项重要的指标。但对于商用通信网而言，由于它被蓄意破坏的可能性很小，网络的抗毁性也就没有那么重要了。 网络的抗毁性与网络部件的可靠性无关，所以它不能完全描述通信网的可靠性，但它指出了通信网可靠性最重要的一个方面网络拓扑结构的可靠性。 网络的粘聚度和连通度

22、可通过图论算法计算出来，算法在给出数值指标的同时，还可以指出哪些链路和哪些节点是最关键的，它们的失效将影响到整个通信网的生存。2.2.2 网络的生存性网络的生存性（Survivability）给出了通信网在随机性破坏作用下的网络可靠性。在军用环境中，随机性破坏表现为“破坏者只具有关于网络结构的部分资料，并采用一种随机的破坏策略”；在商用环境中，随机性破坏则表现为网络部件（节点和链路）的自然失效。网络的生存性由可靠性的概率测度连通概率来表示，它给出通信网在一定意义上的连通概率。在网络生存性的研究中，有一条重要的基本假设是：网络部件之间是相互统计独立的。但在实际通信网中，这种假设可能不存在，如无线

23、电通信网中存在着电磁干扰。网络生存性是基于概率论和图论的知识提出来的，它描述了随机性破坏（主要是网络部件的自然失效）以及网络拓扑结构对通信网可靠性的影响。这里的可靠性实际上是网络的连通性，连通性无论对军用通信网还是商用通信网都是十分重要的，它是通信网最基本的特性。所以，网络生存性是通信网可靠性领域中研究得最多、持续时间最长的课题。2.2.3 网络的有效性无论是网络的抗毁性还是网络的生存性，都只从网络连通性的角度去考察通信网的可靠性，而没有从网络的业务性能（如吞吐量和时延）来研究通信网的可靠性。实际上，通信网的设计者和使用者更关心网络在失效环境中的业务性能。为此，人们提出了网络的有效性（Avai

24、lability）基于网络业务性能的可靠性测度，它指出了通信网在网络部件失效条件下满足通信业务性能要求的程度。网络的有效性探讨了由于网络部件失效引起网络业务性能下降的问题，使通信网可靠性的测度更面向通信、面向用户，更具有直观性，把通信网可靠性的研究工作大大推进了一步。2.3 二端网络的离散概率模型通信网的可靠性是指将所需要的信息从源节点成功地送到终结点的概率。它与网内节点、支柱可靠性、网的拓扑结构及容量有关。为了便于描述和计算，我们用一个图G(V, E)表示通信网。计算机通信网络的拓扑类型较多，但最基本的拓扑类型有6种:星状、树状、网状、环状、总线状和混合状，如图所示。 a）星状 b）树状 c

25、）网状 d）环状 e）总线状 f）混合状图2-1 各种网络拓扑结构符号表示G(V, E)表示二端网络拓扑结构的图，V是图的点集，E是图的边集s源端d终端F(t)二端网络的故障分布函数R(t)二端网络的可靠度分布函数REL(G)离散概率模型下的二端网络可靠度函数xi网络第i个部件的状态值（0或者1）x有n个部件的二端网络状态向量，x=(x0, x1 xn-1)fb()网络状态的布尔函数可靠性工程中，故障分布函数通常被用来描述系统的可靠性，分析系统的故障率、平均故障时间、故障频率等可靠性指标。同样，网络的故障分布函数也可用来分析网络的可靠性，如下是网络故障分布函数的一般定义： (2-1)网络可靠度

26、分布函数可描述为： (2-2)上述只是网络故障分布函数和可靠度分布函数的简单描述，作为一个复杂系统，网络的故障分布是很难描述的。一条链路或者一个结点的故障分布也许比较容易，但从全网的角度去描述故障并不是一件容易的事情。网络故障的原因很多很复杂，譬如，随机的单点故障、多点故障、依赖故障、流量拥塞故障等等。而且，当网络规模很大时，故障描述会随着网络故障数量的膨胀变得极其困难。从大多数网络可靠性文献来看，离散概率模型是分析网络可靠性的有效手段，它既简化了网络的复杂性，又不失一般性。网络可靠性的离散概率模型包括随机图和部件工作概率分布两部分。随机图是指由网络拓扑结构转化来的一个图G=(N, E)，N是

27、图中点的集合，E是图中边的集合，原来网络中路由器转化成图中的点，网络中连接路由器的链路转化成图中的边，图中的点和边有两种状态：工作和故障。部件（点和边）工作概率分布是指部件工作服从0-1分布，第i个部件可用随机变量xi表示，xi =1表示部件工作，其概率为Prxi =1；xi =0表示部件故障，其概率为Prxi =0=1Prxi =1。在上述离散概率模型下，可用随机向量x=(x0, x1, xn-1)来表示n个部件网络G的状态，网络处于状态X的概率可表示为： (2-3)根据部件工作或故障状态，可以得到2n个网络状态，这些状态构成了网络状态空间。从而有如下布尔函数： (2-4)这样，网络的可靠度

28、可如下表示： (2-5)下面的例子进一步解释了网络可靠性的离散概率模型，如图2-2网络的边集和点集分别为，Nv0, v1, v2, v3，E= e0, e1, e2, e3, e4， v0和v3分别是网络的源端和终端，如果这两点保持连通就认为网络可靠。假设结点可靠，那么可靠性分析只考虑边的工作概率。令xi表示边ei的状态，其工作概率为pi 。状态可以用向量x=(x0, x1, x2, x3, x4)来表示，向量(0,1,1,1,1)表示e0故障 e1, e2, e3, e4工作的网络状态，网络处于该状态的概率可以表示为：网络的可靠度计算公式为：图2-2 实例网络2.4 算法比较2.4.1 解析

29、算法给定网络S，对任意两个N点，若弧失效时，这两个节点间无路由相通，则称 为这两个节点间的割集。若 是一个割集，则从C中任意除去一条弧后就不是割集，此时称C为一个最小割集；若 是S的所有割集，=，它表示割集所有的弧 都失效。已知网络的最小割集，则端对端的连通概率为当输入节点与输出节点之间的所有最小路已经求得，下面给出两端口之间的可靠度的算法思路。步骤1 挑出长度为n路的全体利用定理化为不交和步骤2 把由集合运算法化为不交和。1）初始化： 2）在f中取一项，使R；3）f，此步利用已知定理进行简化； 4）f中若还有项，则k=k+1，转B；否则R即为所求。2.4.2 上下界算法1、基本思路设网络G=

30、（N(G)，(G)），其中N(G)为网络节点集，(G)为网络弧集。1）对于N(G)，运用下述分层算法和分节点算法分别计算与，并有2）去及，即可求出网络的最大上限及最小下限。3）网络的上界可靠度算法依赖于网络的分层技术。4）符号标记：G表示源节点到目标节点的网络；O表示源节点代号；n表示目标节点代号；（a，b）表示从节点a到节点b的弧；N(G)表示G的节点集合，N(G)=0，1，2， ，n；(G)：G的弧集合；R(G)表示网络可靠度，R(G)=节点O与节点n连通的概率；X(a，b)表示二进制随机变量，X(a，b)=1，当且仅当弧（a，b）工作正常；表示弧（a，b）的可靠度，（a，b）(G)，；表

31、示G的第k层次，k=1,2，s（s为网络的总层次数）；()表示第k层的可靠度上界，(G)表示网络G的可靠度上界；表示G中节点a的可靠度下界；(G)表示G的可靠度下界，(G)（n为目标节点）；T表示弧集；C表示节点集。2、网络上界可靠度算法对于网络上界可靠度算法，我们要利用深度优先遍历技术对网络进行分层，其分层要去如下所示。1）每一层为网络的一个子集，即2）每层均至少含一条从源节点n到目标节点O之最小路3）每层为串并联结构，从而很容易计算出子网的串并联可靠度R()4）有G=，s为分层数目5）对于任意弧（a，b），下式成立G最终网络可靠度上界为：(G)3、网络下界可靠度算法如果A，B，C是三条给定

32、的路，则根据全概率公式： 为此，我们可以推出下面一个不等式：通过上面的不等式可以计算一个节点jN的下界可靠度。如果弧收敛于一节点，则下界可靠度可以通过将具有最大可靠度的弧分成两条并联弧来计算出：可靠度下界算法描述如下：步骤1 设i=0，并且j=1；步骤2 T=；步骤3 如果T集合中的节点数等于1，则如果T中的节点数是奇数，则 否则，令MAX并将相应的i赋予x，步骤4 如果j = n则得到下界可靠度，R(G) = ，停止计算；否则，j = j + 1，转步骤2第3章 通信网的存储结构设计3.1 图在程序中的表示网络好比一个个的图，有支点和树干构成，现实中网络有各种拓扑结构，常见的有星形、总线形、

33、环形和网状形等。随机图是指由网络拓扑结构转化来的一个图G=(N, E)，N是图中点的集合，E是图中边的集合,实际中点好比终端，边好比通信线路。根据故障分类可分为点不可靠和边不可靠。结合度是指断开网络的两端所需要去掉的最少链路数目；连通度是指断开网络两端所需要去掉的最少结点数目。在本次设计中只考虑边的不可靠，始终认为点是可靠的。3.2 图的定义与术语3.2.1 图的定义图是一种数据元素间为多对多关系的数据结构，加上一组基本操作构成的抽象数据类型。图3-1 简单的网络图ADT Graph数据对象V ：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VRVR=|v,w(-V且P(v,w

34、),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息基本操作P：CreateGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图GDestroyGraph(&G);初始条件：图G存在操作结果：销毁图GLocateVex(G,u);初始条件：图G存在，u一G中顶点有相同特征操作结果：若G中存在顶点u, 则返回该顶点在图中位置；否则返回其它信息。GetVex(G,v);初始条件：图G存在，v是G中某个顶点操作结果：返回v的值。PutVex(&G,v,value);初始条件：图G存在，v是G中某个顶点操作结果：对v赋值valueFirst

35、AdjVex(G,v);初始条件：图G存在，v是G中某个顶点操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”NextAdjVex(G,v,w);初始条件：图G存在,v是G中某个顶点,w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”InsertVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征操作结果：在图G中增添新顶点vDeleteVex(&G,v);初始条件：图G存在，v是G中某个顶点操作结果：删除G中顶点v及其相关的弧InsertAcr(&G,v,w);初始条件：图G存在，v和w是G中两个顶点操作结

36、果：在G中增添弧,若G是无向的，则还增添对称弧DeleteArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点操作结果：在G中删除弧,若G是无向的，则还删除对称弧DFSTraverser(G,v,Visit();初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次。一旦Visit()失败，则操作失败。BFSTRaverse(G,v,Visit();初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次。一旦Visit(

37、)失败，则操作失败。ADT Graph3.2.2 图的常用术语图3-2 有向图和无向图对上图有：G1=(V1,A1)其中：V1=v1,v2,v3,v4 A1=,如果用n表示图中顶点数目，用e表示边或弧的数目，则有：对于无向图，e的取值范围是0到n(n-1)/2,有n(n-1)/2条边的无向图称为完全图。对于有向图，e有取值范围是0到n(n-1)。具有n(n-1)条弧的有向图称为有向完全图。有很少条边或弧的图称为稀疏图，反之称为稠密图。图3-3 各种图v1与v2互为邻接点；e1依附于顶点v1和v2v1和v2相关联；v1的度为3图3-4 度的表示3.3 图的储存结构3.3.1 数组表示法图的存储结

38、构：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。/ 图的数组（邻接矩阵）存储表示#define INFINITY INT_MAX /最大值无穷大#define MAX_VERTEX_NUM 20 /最大顶点个数typedef enumDG,DN,AG,AN GraphKind;/有向图，有向网，无向图，无向网typedef struct ArcCellVRType adj; /VRType是顶点关系类型。对无权图，用1或0表示相邻否，对带权图，则为权值类型InfoType *info; /该弧相关停息的指针ArcCell,AdjMatrixmax_vertex

39、_nummax_vertex_num;tpyedef structVertexType vexsMAX_VERTEX_NUM; /顶点向量AdjMatrix arcs; /邻接矩阵int vexnum,arcnum; /图的当前顶点数和弧数GraphKind kind; /图的种类标志MGraph;图3-5 邻接矩阵表示法3.3.2 邻接表邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个结点由三个域组成，其中邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置，链域(nextarc)指

40、示下一条边或弧的结点；数据域(info)存储和边或弧相关的信息，如权值等。每个链表上附设一个表头结点，包含链域(firstarc)指向链表中第一个结点，还设有存储顶点vi的名或其它有关信息的数据域(data)。如：表结点adjvexnextarcinfo头结点datafirstarc#define MAX_VERTEX_NUM 20typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc; /指向下一条弧的指针InfoType *info; /该弧相关信息的指针ArcNode;typedef struct VNo

41、deVertexType data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; /图的当前顶点数和弧数int vexnum,arcnum; /图的种类标志int kind;ALGraph;3.4 图在程序中的表示3.4.1 点的度表示定义一个结构体，名为dgree_node，其中包含点的度数，各个点在指针中的位置以及点的可靠度。struct dgree_nodeint dgree;int prtadj;float prob;3.4.2

42、邻结点的表示定义一个结构体，名为adjacent_node，其中包含各个点的编号node_id，前后链表的指针位置pre、next以及边的表示ptr_edge。struct adjacent_nodeint node_id;int pre;int next;int idle;int ptr_edge;3.4.3 边的表示定义一个结构体，名为edge，其中包含边的可靠度edgeprob，边所对应的起点和终点from、to以及用flag标记边是否被访问。struct edgefloat edgeprob;int flag;int from,to;3.4.4 保存网络的图结构最后把点的度和邻接点的信

43、息储存在一张完整的图结构中struct dgramstruct dgree_node dgr_tabMAX_LEN;struct adjacent_nodeadj_tab3*MAX_LEN;int num;int len_adjtable;int vidle;int stail;struct edge* edge_tab;int num_edge;3.4.5 网络的储存过程根据输入网络数据创建一个图结构，保存在diagram中，定义名为diag_create的函数。该函数从TXT文档中读取图的信息，储存点的信息，包括点的度数，头指针位置等；储存边的信息，包括每条的两个端点，边的可靠度，边的编号

44、；最后还建立一个邻接表来表示各个点还有边之间的关系，把整个网络规范化。int diag_create( )while(i k & j ma)diagram.adj_tabi.pre = -1;i += (diagram.dgr_tabj.dgree -1);diagram.adj_tabi.next = -1;i+;j+;fclose(fp);diagram.vidle = k;j = k / 2;for(i = 0; i j; i+)diagram.adj_tabk.idle = k + 1;k+;diagram.adj_tabk - 1.idle = -1;diagram.len_adjtable=k-1;diagram.stail=diagram.dgr_tabid_sourcenode.dgree-1;for(i = 0; i ma; i+)printf(num: %4d, degree: %4d, proba: %1.3f, prtadj %4dn,