1、第11章 路由算法与实验 第11章 路由算法与实验 11.1 基本原理基本原理 11.2 Prim算法算法 11.3 Kruskal算法算法 11.4 Dijkstra算法算法 11.5 Floyd算法算法 第11章 路由算法与实验 11.1 基基 本本 原原 理理11.1.1 路由器的定义路由器的定义路由是指通过相互连接的网络把信息从源地点移动到目标地点的活动。一般在路由过程中，信息会经过一个或多个中间节点。普通用户通常容易将路由和交换的概念混淆。其实，两者之间的主要区别就是交换发生在OSI参考模型的第二层(数据链路层)，而路由发生在第三层，即网络层。这一区别决定了路由和交换在移动信息的过程
2、中需要使用不同的控制信息，所以两者实现各自功能的方式是不同的。第11章 路由算法与实验 路由器是互联网络的枢纽，是“交通警察”，是互联网的主要节点设备。路由器通过路由决定数据的转发。转发策略称为路由选择(routing)，这也是路由器名称的由来(router，转发者)。作为不同网络之间互相连接的枢纽，路由器系统构成了基于TCP/IP的国际互联网络Internet的主体脉络，也可以说，路由器构成了Internet的骨架。它的处理速度是网络通信的主要瓶颈之一，其可靠性则直接影响着网络互连的质量。因此，在园区网、地区网乃至整个Internet研究领域中，路由器技术始终处于核心地位，其发展历程和方向成
3、为整个Internet研究的一个缩影。第11章 路由算法与实验 11.1.2 路由器的构成路由器的构成路由器具有四个要素：输入端口、输出端口、交换开关和路由处理器。(1)输入端口是物理链路和输入包的进口。端口通常由线卡提供，一块线卡一般支持4、8或16个端口。一个输入端口具有许多功能：第一个功能是进行数据链路层的封装和解封装；第二个功能是在转发表中查找输入包目的地址并决定目的端口(称为路由查找)，路由查找可以使用一般的硬件来实现，或者通过在每块线卡上嵌入一个微处理器来完成；第三，为了提供QoS(Quality of Service，服务质量)，端口要把收到的包分成几个预定义的服务级别；第四，端
4、口可能需要第11章 路由算法与实验 运行如SLIP和PPP(点对点协议)这样的数据链路级协议，或者如PPTP(Point-to-Point Tunnel Protocol，点对点隧道协议)这样的网络级协议。路由查找完成后，必须用交换开关将包送到其输出端口。如果路由器是输入端队列型的，则几个输入端共享同一个交换开关。这样输入端口的最后一项功能是公共资源(如交换开关)的仲裁协议。第11章 路由算法与实验(2)交换开关可以使用多种不同的技术来实现，使用最多的交换开关技术是总线、交叉开关和共享存储器。总线开关使用一条总线连接所有的输入和输出端口，是最简单的开关，缺点是其交换容量受限于总线的容量以及为共
5、享总线仲裁所带来的额外开销。交叉开关通过开关提供多条数据通路，具有NN个交叉点的交叉开关可以被认为具有2N条总线。如果一个交叉点闭合，则输入总线上的数据在输出总线上可用，否则不可用。交叉点的闭合与打开由调度器来控制，因此，调度器限制了交换开关的速度。在共享存储器路由器中，进来的包被存储在共享存储器中，所交换的仅是包的指针，这提高了交换容量，但是，共享存储器技术交换的第11章 路由算法与实验 速度受限于存储器的存取速度。尽管存储器容量每18个月能够翻一番，但存储器的存取时间每年仅降低5%，这是共享存储器交换开关的固有限制之一。(3)输出端口在数据包被发送到输出链路之前存储数据包，可以实现复杂的调
6、度算法以支持优先级等要求。与输入端口一样，输出端口同样要能支持数据链路层的封装和解封装，以及许多较高级协议。(4)路由处理器通过对转发表进行操作以实现路由协议，并运行对路由器进行配置和管理的软件。同时，它还处理那些目的地址不在线卡的转发表中的数据包。第11章 路由算法与实验 11.1.3 路由器的分类路由器的分类从体系结构上看，路由器可以分为第一代单总线单CPU型路由器、第二代单总线主从CPU型路由器、第三代单总线对称式多CPU型路由器、第四代多总线多CPU型路由器、第五代共享内存式路由器、第六代交叉开关体系路由器和基于机群系统的路由器等多类。从网络级别上看，路由器可以分为接入路由器、企业级路
7、由器、骨干网路由器和太比特路由器四种。接入路由器使得家庭和小型企业可以连接到某个互联网服务提供商；企业级路由器连接一个校园或企业内成千上万的计算机，不但要求端口数目多、价格低廉，而且要求配置起来简单方便，并提供QoS；骨干网路由器终端系统通常是不能直接访问的，第11章 路由算法与实验 它们连接长距离骨干网上的ISP和企业网络，要求路由器能对少数链路进行高速路由转发。在未来核心互联网使用的三种主要技术中，光纤和DWDM都已经是很成熟并且是现成的，如果没有与现有的光纤技术和DWDM技术提供的原始带宽对应的路由器，新的网络基础设施将无法从根本上得到性能的改善，因此开发高性能的骨干交换/路由器(太比特
8、路由器)已经成为一项迫切的要求。太比特路由器技术现在主要还处于开发实验阶段。第11章 路由算法与实验 11.1.4 路由器的功能路由器的功能路由器的一个功能是连通不同的网络，另一个功能是选择信息传送的线路。选择通畅快捷的路径，能大大提高通信速度，减轻网络系统通信负荷，节约网络系统资源，提高网络系统畅通率，从而让网络系统发挥出更大的效益来。一般说来，异种网络的互连与多个子网的互连由路由器来完成。第11章 路由算法与实验 路由器的主要工作是为经过路由器的每个数据帧寻找最佳传输路径，并将该数据有效地传送到目的站点。由此可见，选择最佳路径的策略，即路由算法，是路由器的关键所在。为完成这项工作，在路由器
9、的路由表(Routing Table)中保存着子网的标志信息、网上路由器的个数、下一个路由器的名字等各种传输路径的相关数据。路由表可以是由系统管理员固定设置好的，也可以由系统动态修改；可以由路由器自动调整，也可以由主机控制。第11章 路由算法与实验(1)静态路径表：由系统管理员事先设置好的固定的路径表称之为静态(Static)路径表，一般是在系统安装时就根据网络的配置情况预先设定的，它不会随未来网络结构的改变而改变。(2)动态路径表：动态(Dynamic)路径表是路由器根据网络系统的运行情况而自动调整的路径表。路由器根据路由选择协议(Routing Protocol)提供的功能，自动学习和记忆
10、网络运行情况，在需要时自动计算数据传输的最佳路径。第11章 路由算法与实验 11.1.5 路由选择算法路由选择算法1.设计目标设计目标路由选择算法通常具有下列一个或多个设计要求：(1)最优性。最优性是指路由选择算法选择最优路径的能力。最优路径取决于计量标准和计算权值，例如一个路由选择算法同时考虑途经站点的数目和延迟开销，但在计算过程中更重视延迟开销。因此，路由选择协议必须严格定义其计算方法。(2)简易性和低开销。路由选择算法应尽可能地简单。换言之，路由选择算法必须用最低的软/硬件开销来提供最有效的功能。实现路由选择算法的软件运行在物理资源有限的计算机上，其效率显得尤为重要。第11章 路由算法与
11、实验(3)强壮性和稳定性。路由选择算法必须具有强壮性，这意味着它们必须在出现异常或非预见性情况(如硬件故障,高负荷状态和不正确的操作)时也能正常运行。由于路由器位于网络连接点上，发生故障时会引起更为严重的问题，因此，路由选择算法必须经受时间的考验，且在各种不同的网络环境下有很好的稳定性。第11章 路由算法与实验(4)快速收敛性。路由选择算法必须能够迅速收敛。收敛是指所有路由器都承认新的最优路由的过程。当一个网络由于某种事件造成路由设备停机或开通时，路由器就会发送修正的路由消息，该消息在网络上传播，引发路由器重新计算最优路由，并最终促使所有路由器承认新的最优路由。路由选择算法收敛过慢，会导致路由
12、循环或网络发生故障。例如假设数据包在时间t1到达路由器1，此时路由器1已经被更新，它知道的到达目的节点的路由是最优路由，该路由要求路由器2成为下一个节点。因此，路由器1转发数据包到路由器2。但如果路由器2还未被更新，它认为最优路由的下一个节点是路由器1。路由器2又把数据包送回到路由器1。这样,数据包持续在这两个路由器之间来回传送，直到路由器2收到路由修正命令或者达到数据包允许转发的最大次数为止。第11章 路由算法与实验(5)灵活性。这意味着路由选择算法必须迅速准确地适应不同的网络环境。例如假设某一网段失败，路由选择算法在意识到这个问题后，应能尽快为所有路由选择最佳路径，避免使用那段网络。路由选
13、择算法在设计时应能适应网络带宽、路由器队列大小和网络延迟等变化。第11章 路由算法与实验 2.路由选择算法类型路由选择算法类型按类型划分，路由选择算法主要包括以下几种：1)静态和动态路由选择算法严格地说，静态路由选择算法不是一种算法，因为网络管理员在路由选择开始前就已建立了映射表，如果网络管理员不改变它们，映射将保持不变。静态路由选择算法设计简单，并在网络信息流相对可以预见且网络设计相对简单的环境里效果较好。第11章 路由算法与实验 由于静态路由选择算法不能对网络的变化作出反映，所以，它不适应当今大型、易变的网络环境的需求。20世纪90年代以来，绝大多数优秀的路由选择算法都是动态的，这些动态路
14、由选择算法通过分析接收到的路由修正消息适应网络环境的变化。当路由器接收到网络发生变化的消息后，就会重新计算路由，并向其他路由器发出路由修正消息。其他的路由器接收到这些消息后，将重复上述过程直至所有路由器的路由表更新完毕。静态路由选择算法可以弥补动态路由选择算法的某些不足。例如为所有无法选择路由的数据包指定一个最终路由器，即将所有无法选择路由的数据包转发到该路由器来，以保证所有数据包都得到某种方式的处理。第11章 路由算法与实验 2)单路径和多路径路由选择算法一些复杂的路由选择协议支持多路径到达同一目的节点，与单路径算法不同，这些多路径算法允许信息流在多条线上进行复制。多路径算法的优势是提高了数
15、据吞吐率和可靠性。3)平面和分层路由选择算法一些路由选择算法在平面空间运行，而另一些路由选择算法采用分层空间运行。在平面路由选择算法中，所有路由器是对等的，而在分层路由选择算法中，路由器被划分成主干路由器和非主干路由器。来自非主干路由器的数据包先被传送到主干路由器中，然后通过主干路由器转发到目的节点域，最后通过一个或多个非主干路由器到达目的节点。第11章 路由算法与实验 路由系统常将逻辑节点组称为域、自主系统或区域。在分层路由选择算法中，任一域中只有一部分路由器可以与其他域中的路由器通信，而其他路由器只能与该域中的路由器通信。在超大型的网络中，可能还存在更多的层次，一般都是位于最高层的路由器形
16、成路由器的主干。分层路由类似公司的组织结构，其主要优点是能较好地支持信息流模式。由于大多数网络通信发生在小公司群(域)中，且域内路由器只需要了解域内的其他路由器即可。因此，可以简化它们的路由选择算法，以相应地减少路由修正消息流的发布。第11章 路由算法与实验 4)主机智能和路由器智能路由选择算法一些路由选择算法假定源节点决定整个发送路由，这就是通常所说的源路由选择(source routing)。在源路由选择系统里，路由器只是一个存储和发送设备，负责向下一节点发送数据包。在这种系统中，主机具有路由选择的智能。其他算法假定主机对路由器一无所知，路由器根据自己计算的结果来确定互联网上的路径。在这种
17、系统中，路由器具有路由选择的智能。第11章 路由算法与实验 虽然主机智能路由选择算法在实际发送数据包之前就能发现到达目的节点的所有可能的路由，并能根据不同系统对最优路由的不同要求做出选择，但这种选择所有路径的方法常常需要耗费大量的时间。如果把主机智能路由选择算法与路由器智能路由选择算法结合起来使用，则是一种较好的方法。5)域内和域间路由选择算法一些路由选择算法只在域内运行，而另一些路由选择算法可在域内或域间运行。这两种算法在本质上存在不同。因此，一个最优的域内路由选择算法并不一定是最优的域间路由选择算法。第11章 路由算法与实验 6)链接状态和距离向量路由算法链接状态路由算法(也称做最短路径优
18、先算法)将路由信息发送至互联网络的所有节点上，每个路由器只能传递描述其自身链接状态的那部分路由表。距离向量路由算法(也称做贝尔曼福特算法)要求每个路由器将路由表的全部或部分传送到与其相邻的路由器中。实际上，链接状态路由算法的更新消息只传送路由表更新的部分，而距离向量路由算法的更新消息将路由表的大部分或全部传送到与其相邻的路由器中。第11章 路由算法与实验 由于链接状态路由算法收敛速度较快，因此，它比距离向量路由选择算法更易避免路由循环。但由于链接状态路由算法需要占用更多的CPU和内存资源，因此，它比距离向量路由算法更难以支持和实现。总的来说，这两种算法在大多数情况下运行良好。第11章 路由算法
19、与实验 3.路由选择计量标准路由选择计量标准路由选择算法使用许多不同的计量标准确定最优路由，一些复杂的路由选择算法将多种计量标准融为一体。常用的计量标准有如下几种：(1)路径长度。路径长度(path length)是最普通的一种计量标准。在路由选择协议允许网络管理员为每条网络链路分配任意权值的情况下，路径长度是指所经过的每条链路的权值之和。在路由选择协议定义了站点数目的情况下，路径长度是指数据包从源节点到目的节点过程中通过网络产品(如路由器)的数目。第11章 路由算法与实验(2)可靠性。可靠性(reliability)是指每个网络链路的可靠性(通常用比特错误率描述)，即网络链路是否容易出现网络
20、故障，一旦发生故障，是否能迅速修复。在进行可靠性等级分配时，应考虑所有影响可靠性的因素。通常由网络管理员给网络链路分配可靠性等级，而这些等级一般用数值表示。(3)路由选择延迟。路由选择延迟(routing delay)指的是通过互联网络从源节点发送数据包到目标节点所需的时间。延迟时间取决于诸多因素，其中包括网络链路的带宽及网络堵塞程度、沿途每个路由器端口的队列和传输的物理距离等。由于延迟受几种重要因素的影响，因此，它是一种应用最广且最有用的计量标准。第11章 路由算法与实验(4)带宽。带宽(bandwidth)是指链路传输信息流的能力。在所有其他条件相同的情况下，10 Mb/s以太网链路显然优
21、于64 kb/s的租用链路。尽管带宽越大表示链路的传输能力越强，但通过较大带宽链路的路由并不一定比通过较慢链路的路由更好，因为如果较快的链路非常繁忙，那么，通过它向目的节点传送数据包所需的实际时间可能会更长。(5)负载。负载(load)是指网络资源(如路由器)的繁忙程度，它可用多种方式进行计算，其中包括CPU的利用率和每秒处理数据包的次数。当然，持续不断地监控这些负载参数本身就要占用资源。第11章 路由算法与实验(6)通信开销。通信开销(communication cost)是另外一种重要的计量标准，尤其是当公司关心运行费用胜过运行性能时。对于这些公司来说，他们宁可将数据包在自己的链路上进行传
22、输(即使这样可能增加链路延迟)，也不愿花钱(省时间)在公用链路上传输。4.路由选择算法路由选择算法路由选择算法包括以下几种算法：Prim算法、Kruskal算法、Dijkstra算法、Floyd算法等。下面依次介绍。第11章 路由算法与实验 11.1.6 图论基础知识图论基础知识1.图的基本概念图的基本概念在介绍路由器算法之前，先介绍一些图论的基础知识。简单地说，图是一个包含了点和点间连线的集合。习惯上用G=(V，E)代表一个图，图中的节点又称顶点，V是节点的有穷(非空)集合，通常称节点的偶对为边，E是边的集合。图中代表一条边的节点偶对是无序的，则称此图为无向图。在无向图中，(v1，v2)和(
23、v2，v1)代表同一条边，如图11.1所示。第11章 路由算法与实验 图11.1 无向图 第11章 路由算法与实验 图中代表一条边的节点偶对是有序的，则称此图为有向图。在有向图中，表示一条有向边，v1称为边的始点，v2称为边的终点。和表示不同的边，如图11.2所示。图11.2 有向图 第11章 路由算法与实验 图在实际应用时通常需要说明其他信息，这些信息可以附加到图的边或顶点上。用某种形式标识的图称为标号图。图11.3为标号图的两个例子。图11.3 标号图(a)顶点带标号的有向图；(b)边带标号的无向图第11章 路由算法与实验 2.图的表示法 有向图 G=(V,E)，由于 EVV，图中最多包含
24、|V|2条边。对于给定顶点集 V，可能有2V2个边集。因此，设计一个图的表示方法时，主要问题是如何适当地描述这个边集。假设有一个具有 n 个顶点的有向图 G=(V，E)，Vv1，v2，vn。用一个 nn 阶的 0-1 矩阵 A 描述，即其他0E)v,(v1Ajiji,，即仅当 vi?vj是 G 的一条边时，矩阵的第(i,j)个元素才为 1。这个 A 矩阵称为相邻矩阵。第11章 路由算法与实验 图 11.2 所示的有向图的相邻矩阵为1000100101000110A。相邻矩阵亦可描述无向图，由于(v1,v2)(v2,v1)，所以相邻矩阵是对称矩阵，且对角线上的元素都为 0。图11.1 所示的无向
25、图的相邻矩阵为0100101101010110A。第11章 路由算法与实验 把相邻矩阵加以变化，可以表示边带标号的图，把不存在的边对应的矩阵项设置为?，其他值为标号图中的标识。例如图11.3 所示的边带标号的无向图的相邻矩阵为 2626594159314131A.第11章 路由算法与实验 3.图的实现图的实现我们把图看做是一类特殊的容器，在正规的情况下，图G=(V,E)是由两个集合(顶点集合和边集合)组成的序偶。在不正规情况下，图是一个有两个分隔仓的容器，一个为顶点，一个为边。因此存在三种对象，即顶点、边、图。相应地，需要三个对象类：顶点类(Vertex)、边类(Edge)和图类(Graph)
26、，如图11.4所示。第11章 路由算法与实验 图11.4 对象类层次第11章 路由算法与实验 1)顶点的实现在一个图中的各个顶点必须相互区别，即给顶点按顺序标号。类Vertex是从基类Object中派生出来的，声明了单一成员变量number，对应于插入图中的每一个顶点的不同编号。class Vertex:public Object public:typedef unsigned int Number;protected:Number number;public:Vertex(Number);第11章 路由算法与实验 Virtual operator Number()const;/;该程序定义了
27、一个类 Vertex 的构造函数，这个构造函数只有一个赋给顶点编号的参数。另外，程序还声明了一个转换成编号的成员函数 operator Number，允许程序员在有整数的地方使用顶点，返回的是成员变量 number 的值。第11章 路由算法与实验 2)边的实现在有向图中边是顶点的一个序偶，在无向图中边是一个含两个顶点的集合。由于概念的相似性，对它们使用相同的类，由边的具体使用来定义是有向边还是无向边。类Edge是从基类Object中派生出来的。class Edge:public Object protected:Vertex&v0;Vertex&v1;public:Edge(Vertext&,
28、Vertex&);Virtual Vertex&V0()const;第11章 路由算法与实验 Virtual Vertex&V1()const;Virtual Vertex&Mate(Vertex const&)const;/;类 Edge 包含两个变量 v0和 v1，分别为一个顶点的引用。当这类的实例用于描述一条有向边时，可表示 v0v1。当这类的实例用于描述一条无向边时，可表示为v0,v1。程序声明了一个构造函数，带有两个参数，均为 Vertex 实例引用。这个构造函数的作用是对两个相应的成员变量进行初始化。第11章 路由算法与实验 除了构造函数，程序还有三个公共成员函数：V0、V1、Ma
29、te，它们是访问者函数，前两个用于访问成员变量 v0和 v1。对于类 Edge 的任何实例 e，Mate 成员函数满足：e.Mate(e.v0()?e.V1()e.Mate(e.v1()?e.V0()因此如果知道顶点 v 是 e 的一个顶点，通过调用 e.Mate(v)就能找到其他顶点。第11章 路由算法与实验 3)图的实现有向图和无向图有很多共同特点，因此在图类的实现中利用继承性似乎是顺理成章的。我们可以把有向图视做附有箭头的无向图。抽象类Graph和Digraph中，Graph是基类，描述无向图的具体类是由它派生的，Digraph拓宽了Graph，描述有向图的具体类就是它派生的。第11章
30、路由算法与实验 class Graph:public Container protected:unsigned int numberOfVertices;unsigned int numberOfEdges;void DepthFirstTraversal(PrePostVisitor&,Vertex&,Array&)const;public:Graph();第11章 路由算法与实验 virtual unsigned int numberOfEdges()const;virtual unsigned int numberOfVertices()const;virtual void AddVer
31、tex(Vertex&)=0;virtual Vertex&SelectVertex(Vertex:Number)const=0;virtual Vertex&operator(Vertex:Number)const;virtual void AddEdge(Edge&)=0;virtual Edge&SelectEdge(Vertex:Number,Vertex:Number)const=0;virtual bool IsEdge(Vertex:Number,Vertex:Number)const=0;virtual bool IsConnected()const;virtual bool
32、IsCyclic()const;第11章 路由算法与实验 virtual Iterator&Vertices()const=0;virtual Iterator&Edges()const=0;virtual Iterator&IncidentEdges(Vertex const&)const=0;virtual Iterator&EmanatingEdges(Vertex const&)const=0;virtual void DepthFirstTraversal(PrePostVisitor&,Vertex const&)const;virtual void BreadthFirstTra
33、versal(Visitor&,Vertex const&)const;/;第11章 路由算法与实验 class Digraph:public virtual Graph public:virtual bool IsConnected()const;virtual bool IsCyclic()const;virtual void TopologicalOrderTraversal(Visitor&)const;第11章 路由算法与实验 Graph是一个包含了纯虚拟成员函数的抽象类，它在从基类继承过来的成员变量中增加了两个新的成员变量numberOfVertices和numberOfEdges
34、。Graph还声明了一个缺省的构造函数，这个构造函数的作用是把类的两个成员变量初始化为0。因此，最初图是空的既没有边，也没有顶点。Graph类声明了下列存取器(accessor)和变更器(mutator)的成员函数：NumberOfEdges：返回图包含的边的数量(存取器)。NumberOfVertices：返回图包含的顶点的数量(存取器)。AddVertex：把某个给定的顶点插入图中(变更器)。第11章 路由算法与实验 SelectVertex：带有一个整型参数，如i(0in)，并返回第i个顶点的引用(存取器)。operator：下标操作函数，带有一个整型值的下标表达式参数，其缺省操作是调用
35、SelectVertex函数。AddEdge：把某个给定的边插入图中(变更器)。IsEdge：布尔型函数，带有两个Vertex:Number参数。如果图中有一条连接相应顶点的边，就返回true(存取器)。SelectEdge：带有两个Vertex:Number参数。返回一个连接相应顶点的边的实例引用，当边不存在时，它的行为未定义。IsCyclic：如果图中有回路，返回true。IsConnect：如果图是连通的，返回true。第11章 路由算法与实验 下列每一个成员函数都将动态分配一个迭代器实例。(1)Vertices：类Graph的成员函数，返回一个遍历V中元素的迭代器。(2)Edges：类
36、Graph的成员函数，返回一个遍历E中元素的迭代器。(3)IncidentEdge：这个成员函数带有一个指向顶点v的引用参数，返回一个遍历v的射入集中元素的迭代器。(4)EmanatingEdges：这个成员函数带有一个指向顶点v的引用参数，返回一个遍历v的射出集中元素的迭代器。第11章 路由算法与实验 下列是Graph类中声明的图的遍历函数，作用是保证图中所有的顶点都将被系统访问。(1)DepthFirstTraversal和BreadthFirstTraversal：这两个遍历函数带有两个参数，一个为Visitor对象的引用，另一个为顶点的引用。顶点规定了深度优先遍历或广度优先遍历的起始顶
37、点。(2)TopologicalOrderTraversal：拓扑排序是对有向图节点所做的排序，拓扑排序遍历将按照拓扑排序规定的顺序来遍历图中的节点。因此，它是类Digraph的一个成员函数。第11章 路由算法与实验 4)无向图的实现类GraphAsMatrix是基类Graph的派生类，它用相邻矩阵描述图的边。由于类GraphAsMatrix是个具体类，所以必须提供基类中所有被定义为纯虚拟函数的具体实现，为简单起见，下面的程序删去了它的函数原型。class GraphAsMatrix：public virtual Graph protected:Array vertices;Array2D a
38、djacencyMatrix;public:GraphAsMatrix(unsigned int);/.;第11章 路由算法与实验 类GraphAsMatrix的每一个实例都表示一个无向图，如G=(V,E)。它的两个成员变量vertices和adjacencyMatrix分别用于描述集合V和集合E。顶点集V用一个指向Vertex实例的一维指针数组描述，边集E用一个指向Edge实例的二维指针矩阵(数组)描述。GraphAsMatrix构造函数只有一个unsigned int类型的参数，这个参数规定了图可能包含的最大顶点数。它的值确定了顶点数组的长度及相邻矩阵的维度。第11章 路由算法与实验 4.
39、图的遍历图的遍历图有很多方面的应用，因此有许多不同的算法来操纵它们，但是这些算法都必须能系统访问图中的所有节点(顶点)，即图的各种算法都要遍历图这种数据结构，并在每一个顶点处执行某种操作。这种遍历图的过程称为图的遍历(Graph Traversal)。常用的图的遍历有三种：深度优先遍历(Depth-first Traversal)、广度优先遍历(Breadth-first Traversal)和拓扑排序(Topological Sort)。这里只介绍前两种遍历方法。第11章 路由算法与实验 1)深度优先遍历图的深度优先遍历是访问一个顶点，然后递归地访问邻接于此节点的所有顶点，而问题在于图可能有
40、回路，并且遍历时访问每一个顶点的次数最多只能有一次，解决的方法是记录已访问过的节点，以使遍历不至于无限地递归进行。在图11.2中如果遍历从顶点c开始，则访问节点的顺序为：c、a、b、d。下面给出了两个深度优先遍历的子程序DepthFirst Traversal的实现代码。第一个是带两个参数的，这个子程序声明为public；另外一个带三个参数，这个子程序声明为protected。第11章 路由算法与实验 void Graph:DepthFirstTraversal(prePostVisition&visitor,Vertex const&start)const Array visited(num
41、berOfVertices);for(Vertex:Number v=0;vnumberOfVertices;+v)visitedv=false;DepthFirstTraversal(visitor,const_cast,(start)visited);第11章 路由算法与实验 void Graph:DepthFirstTraversal(prePostVisition&visitor,Vertex&vertex,Array&visited)const if(visitor.IsDone()return;visitor.PreVisit(vertex);visitedvertex=true;
42、Iterator&p=EmanatingEdge(vertex);第11章 路由算法与实验 while(!p.IsDone()Edge&edge=dynamic_cast(*p);Vertex&to=edge.Mate(vertex);if(!visitedto)DepthFirstTraversal(visitor,to,visited);+p;delete&p;visitor.PostVisit(vertex);第11章 路由算法与实验 2)广度优先遍历图的广度优先遍历首先访问深度为0的节点(根节点)，然后访问深度为1的节点，依此类推。所谓深度，是指从起始顶点到给定顶点的最短路线长度。由于
43、图没有根节点，必须确定遍历从哪个顶点开始。这样，广度优先遍历首先访问起始顶点，然后访问所有与起始顶点相邻的顶点，再访问所有与那些相邻顶点相邻的顶点，依此类推。图11.5是对图11.2所示的有向图进行广度优先遍历的过程。从顶点a开始的广度优先遍历访问的顺序为a、b、c、d。第11章 路由算法与实验 图11.5 广度优先遍历过程第11章 路由算法与实验 下面给出广度优先遍历子程序 BreadthFirstTraversal 的实现代码，有两个参数，分别指向 Visitor 实例的引用和 Vertex 实例的引用。void Graph:BreadthFirstTraversal(Visitor&vi
44、sitor,Vertex const&start)const Array enqueued(numberOfVertices);for(Vertex:Number v=0;vnumberOfVertices;+v)Enqueuedv=false;Queue&queue=*new QueueAsLinkedList();第11章 路由算法与实验 queue.RescindOwnership();enqueuedstart=true;queue.Enqueue(const_cast(start);while(!queue.IsEmpty()&!visitor.IsDone()Vertex&vert
45、ex=dynamic_cast(queue.Dequeue();visitor.Visit(vertex);Iterator&p=EmanatingEdges(vertex);while(!p.IsDone()第11章 路由算法与实验 Edge&edge=dynamic_cast(*p);Vertex&to=edge.Mate(vertex);if(!enqueuedto)enqueuedto=ture;queue.Enqueue(to);+p;delete&p;delete&queue;第11章 路由算法与实验 11.2 Prim算法算法11.2.1 Prim算法原理算法原理假设G=(V,E
46、)是一个具有n个顶点的边带权无向图，T=(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点(假定取v1)，将它并入U中，此时U=v1；然后只要U是V的真子集(即UV)，就从那些其一个端点已在T中,另一个端点仍在T外的所有边中，找一条最短(即权值最小)边，假定为(vi，vj)，其中viU，vjVU，并把该边(vi，vj)和顶点vj分别并入T的边集TE和顶点集U；如此进行下去,每次往生成树里并入一个顶点和一条边，直到n1次后就把第11章 路由算法与实验 所有n个顶点都并入到生成树T的顶点集中，此时U=V，TE中含有n1条边，
47、T就是最后得到的最小生成树。Prim算法的关键之处是：每次如何从生成树T中到T外的所有边中，找出一条最短边。例如，在第k次前，生成树T中已有k个顶点和k1条边，此时T中到T外的所有边数为k(nk)，当然它包括两顶点间没有直接边相连，其权值被看做“无穷大”的边在内，从如此多的边中查找最短边，其时间复杂性为O(k(nk)，显然是很费时的。是否有一种好的方法能够降低查找最短边的时间复杂性呢？回答是肯定的，它能够使查找最短边的时间复杂性降低到O(nk)。方法是：假定在进行第k次前已经保留着从T中到T外每一顶点(共n第11章 路由算法与实验 k个顶点)的各一条最短边，进行第k次时，首先从这nk条最短边中
48、，找出一条最最短的边(它就是从T中到T外的所有边中的最短边)，假设为(vi，vj)，此步需进行nk次比较；然后把边(vi，vj)和顶点vj分别并入T中的边集TE和顶点集U中，此时T外只有n(k+1)个顶点，对于其中的每个顶点vt,若(vj，vt)边上的权值小于已保留的从原T中到vt的最短边的权值，则用(vj，vt)修改，使从T中到T外顶点vt的最短边为(vj，vt)，否则保持原有最短边不变，这样，就把第k次后从T中到T外每一顶点vt的各一条最短边都保留下来了，为进行第k+1次运算做好了准备，此步需进行nk1次比较。所以，利用此方法求第k次的最短边共需比较2(nk)1次，即时间复杂性为O(nk)
49、。第11章 路由算法与实验 初始态 U =vl TE =LW =(v1,v2)8,(v1,v3)?,(v1,v4)5,(v1,v5)?,(v1,v6)?,(v1,v7)?第一次 U =vl,v4 TE =(v1,v4)5 LW =(v4,v2)3,(v1,v3)?,(v1,v4)5,(v4,v6)7,(v4,v7)15 第二次 U =vl,v4,v2 TE =(v1,v4)5,(v4,v2)3 LW =(v2,v3)12,(v2,v5)10,(v4,v6)7,(v4,v7)15 第三次 U =vl,v4,v2,v6 TE =(v1,v4)5,(v4,v2)3,(v4,v6)7 LW =(v6,
50、v3)2,(v6,v5)9,(v4,v7)15 第11章 路由算法与实验 第四次 U =vl,v4,v2,v6,v3 TE =(v1,v4)5,(v4,v2)3,(v4,v6)7,(v6,v3)2 LW =(v3,v5)6,(v4,v7)15 第五次 U =vl,v4,v2,v6,v3,v5 TE =(v1,v4)5,(v4,v2)3,(v4,v6)7,(v6,v3)2,(v3,v5)6 LW =(v4,v7)15 第六次 U =vl,v4,v2,v6,v3,v5,v7 TE =(v1,v4)5,(v4,v2)3,(v4,v6)7,(v6,v3)2,(v3,v5)6,(v4,v7)15 LW
