第11章路由算法与实验

1、第第1111章章 路由算法与实验路由算法与实验 第第1111章章 路由算法与实验路由算法与实验 11.1 基本原理基本原理 11.2 Prim算法算法11.3 Kruskal算法算法11.4 Dijkstra算法算法11.5 Floyd算法算法思考题思考题第第1111章章 路由算法与实验路由算法与实验 11.1 基本原理基本原理 11.1.1 路由器的定义路由器的定义路由是指通过相互连接的网络把信息从源地点移动到目标地点的活动。一般在路由过程中，信息会经过一个或多个中间节点。普通用户通常容易将路由和交换的概念混淆。其实，两者之间的主要区别就是交换发生在OSI参考模型的第二层(数据链路层)，而路

2、由发生在第三层，即网络层。这一区别决定了路由和交换在移动信息的过程中需要使用不同的控制信息，所以两者实现各自功能的方式是不同的。第第1111章章 路由算法与实验路由算法与实验 路由器是互联网络的枢纽，是“交通警察”，是互联网的主要节点设备。路由器通过路由决定数据的转发。转发策略称为路由选择(routing)，这也是路由器名称的由来(router，转发者)。作为不同网络之间互相连接的枢纽，路由器系统构成了基于TCP/IP的国际互联网络Internet的主体脉络，也可以说，路由器构成了Internet的骨架。它的处理速度是网络通信的主要瓶颈之一，其可靠性则直接影响着网络互连的质量。因此，在园区网、

3、地区网乃至整个Internet研究领域中，路由器技术始终处于核心地位，其发展历程和方向，成为整个Internet研究的一个缩影。第第1111章章 路由算法与实验路由算法与实验 11.1.2 路由器的构成路由器的构成路由器具有四个要素：输入端口、输出端口、交换开关和路由处理器。(1) 输入端口是物理链路和输入包的进口。端口通常由线卡提供，一块线卡一般支持4、8或16个端口，一个输入端口具有许多功能：第一个功能是进行数据链路层的封装和解封装；第二个功能是在转发表中查找输入包目的地址并决定目的端口(称为路由查找)，路由查找可以使用一般的硬件来实现，或者通过在每块线卡上嵌入一个微处理器来完成；第三，为

4、了提供QoS(Quality of Service，服务质量)，端口要把收到的包分成几个预定义的服务级别；第第1111章章 路由算法与实验路由算法与实验 第四，端口可能需要运行如SLIP和PPP(点对点协议)这样的数据链路级协议，或者如PPTP(Point-to-Point Tunnel Protocol，点对点隧道协议)这样的网络级协议。路由查找完成后，必须用交换开关将包送到其输出端口。如果路由器是输入端队列型的，则几个输入端共享同一个交换开关。这样输入端口的最后一项功能是公共资源(如交换开关)的仲裁协议。第第1111章章 路由算法与实验路由算法与实验 (2) 交换开关可以使用多种不同的技术

5、来实现，使用最多的交换开关技术是总线、交叉开关和共享存储器。总线开关使用一条总线连接所有的输入和输出端口，是最简单的开关，缺点是其交换容量受限于总线的容量以及为共享总线仲裁所带来的额外开销。交叉开关通过开关提供多条数据通路，具有NN个交叉点的交叉开关可以被认为具有2N条总线。如果一个交叉点闭合，则输入总线上的数据在输出总线上可用，否则不可用。交叉点的闭合与打开由调度器来控制，因此，调度器限制了交换开关的速度。在共享存储器路由器中，进来的包被存储在共享存储器中，所交换的仅是包的指针，这提高了交换容量，但是，共享存储器技术交换的速度受限于存储器的存取速度。尽管存储器容量每18个月能够翻一番，但存储

6、器的存取时间每年仅降低5%，这是共享存储器交换开关的固有限制之一。第第1111章章 路由算法与实验路由算法与实验 (3) 输出端口在数据包被发送到输出链路之前存储数据包，可以实现复杂的调度算法以支持优先级等要求。与输入端口一样，输出端口同样要能支持数据链路层的封装和解封装，以及许多较高级协议。(4) 路由处理器通过对转发表进行操作以实现路由协议，并运行对路由器进行配置和管理的软件。同时，它还处理那些目的地址不在线卡的转发表中的数据包。第第1111章章 路由算法与实验路由算法与实验 11.1.3 路由器的分类路由器的分类从体系结构上看，路由器可以分为第一代单总线单CPU型路由器、第二代单总线主从

7、CPU型路由器、第三代单总线对称式多CPU型路由器、第四代多总线多CPU型路由器、第五代共享内存式路由器、第六代交叉开关体系路由器和基于机群系统的路由器等多类。从网络级别上看，路由器可以分为接入路由器、企业级路由器、骨干网路由器和太比特路由器四种。接入路由器使得家庭和小型企业可以连接到某个互联网服务提供商；企业级路由器连接一个校园或企业内成千上万的计算机，不但要求端口数目多、价格低廉，而且要求配置起来简单方便，并提供QoS；骨干网路由器终端系统通常是不能直接访问的，它们连接长距离骨干网上的ISP和企业网络，要求路由器能对少数链路进行高速路由转发。 第第1111章章 路由算法与实验路由算法与实验

8、 在未来核心互联网使用的三种主要技术中，光纤和DWDM都已经是很成熟并且是现成的，如果没有与现有的光纤技术和DWDM技术提供的原始带宽对应的路由器，新的网络基础设施将无法得到性能上根本的改善，因此开发高性能的骨干交换/路由器(太比特路由器)已经成为一项迫切的要求。太比特路由器技术现在主要还处于开发实验阶段。11.1.4 路由器的功能路由器的功能路由器的一个功能是连通不同的网络，另一个功能是选择信息传送的线路。选择通畅快捷的路径，能大大提高通信速度，减轻网络系统通信负荷，节约网络系统资源，提高网络系统畅通率，从而让网络系统发挥出更大的效益来。第第1111章章 路由算法与实验路由算法与实验 一般说

9、来，异种网络的互连与多个子网的互连由路由器来完成。路由器的主要工作是为经过路由器的每个数据帧寻找最佳传输路径，并将该数据有效地传送到目的站点。由此可见，选择最佳路径的策略，即路由算法，是路由器的关键所在。为完成这项工作，在路由器的路由表(Routing Table)中保存着子网的标志信息、网上路由器的个数、下一个路由器的名字等各种传输路径的相关数据。路由表可以是由系统管理员固定设置好的，也可以由系统动态修改；可以由路由器自动调整，也可以由主机控制。第第1111章章 路由算法与实验路由算法与实验 (1) 静态路径表：由系统管理员事先设置好的固定的路径表称之为静态(Static)路径表，一般是在系

10、统安装时就根据网络的配置情况预先设定的，它不会随未来网络结构的改变而改变。(2) 动态路径表：动态(Dynamic)路径表是路由器根据网络系统的运行情况而自动调整的路径表。路由器根据路由选择协议(Routing Protocol)提供的功能，自动学习和记忆网络运行情况，在需要时自动计算数据传输的最佳路径。第第1111章章 路由算法与实验路由算法与实验 11.1.5 路由选择算法路由选择算法1. 设计目标设计目标路由选择算法通常具有下列一个或多个设计要求：(1) 最优性。最优性是指路由选择算法选择最优路径的能力。最优路径取决于计量标准和计算权值，例如一个路由选择算法同时考虑途经站点的数目和延迟开

11、销，但在计算过程中更重视延迟开销。因此，路由选择协议必须严格定义其计算方法。第第1111章章 路由算法与实验路由算法与实验 (2) 简易性和低开销。路由选择算法应尽可能地简单。换言之，路由选择算法必须用最低的软/硬件开销来提供最有效的功能。实现路由选择算法的软件运行在物理资源有限的计算机上，效率显得尤为重要。(3) 强壮性和稳定性。路由选择算法必须具有强壮性，这意味着它们必须在出现异常或非预见性情况时(如硬件故障，高负荷状态和不正确的操作)也能正常运行。由于路由器位于网络连接点上，发生故障时会引起更为严重的问题。因此，路由选择算法必须经受时间的考验，且在各种不同的网络环境下有很好的稳定性。第第

12、1111章章 路由算法与实验路由算法与实验 (4) 快速收敛性。路由选择算法必须能够迅速收敛。收敛是指所有路由器都承认新的最优路由的过程。当一个网络由于某种事件造成路由设备停机或开通时，路由器就会发送修正的路由消息，该消息在网络上传播，引发路由器重新计算最优路由，并最终促使所有路由器承认新的最优路由。路由选择算法收敛过慢，会导致路由循环或网络发生故障。例如假设数据包在时间t1到达路由器1，此时路由器1已经被更新，它知道的到达目的节点的路由是最优路由，该路由要求路由器2成为下一个节点。因此，路由器1转发数据包到路由器2。第第1111章章 路由算法与实验路由算法与实验 但如果路由器2还未被更新，它

13、认为最优路由的下一个节点是路由器1。路由器2又把数据包送回到路由器1。这样，数据包持续在这两个路由器之间来回传送，直到路由器2收到路由修正命令或者达到数据包允许转发的最大的次数为止。(5) 灵活性。这意味着路由选择算法必须迅速准确地适应不同的网络环境。例如假设某一网段失败，路由选择算法在意识到这个问题后，应能尽快为所有路由选择最佳路径，避免使用那段网络。路由选择算法在设计时应能适应网络带宽，路由器队列大小和网络延迟等变化。第第1111章章 路由算法与实验路由算法与实验 2. 路由选择算法类型路由选择算法类型按类型划分，路由选择算法主要包括以下几种：1) 静态和动态路由选择算法静态和动态路由选择

14、算法严格地说，静态路由选择算法不是一种算法，因为网络管理员在路由选择开始前就已建立了映射表，如果网络管理员不改变它们，映射将保持不变。静态路由选择算法设计简单，并在网络信息流相对可以预见且网络设计相对简单的环境里效果较好。第第1111章章 路由算法与实验路由算法与实验 由于静态路由选择算法不能对网络的变化作出反映，所以，它不适应当今大型、易变的网络环境的需求。20世纪90年代以来，绝大多数优秀的路由选择算法都是动态的，这些动态路由选择算法通过分析接收到的路由修正消息适应网络环境的变化。当路由器接收到网络发生变化的消息后，就会重新计算路由，并向其他路由器发出路由修正消息。其他的路由器接收到这些消

15、息后，将重复上述过程直至所有路由器的路由表更新完毕。第第1111章章 路由算法与实验路由算法与实验 静态路由选择算法可以弥补动态路由选择路算法的某些不足。例如为所有无法选择路由的数据包指定一个最终路由器，即将所有无法选择路由的数据包转发到该路由器来，以保证所有数据包都得到某种方式的处理。2) 单路径和多路径路由选择算法单路径和多路径路由选择算法一些复杂的路由选择协议支持多路径到达同一目的节点，与单路径算法不同，这些多路径算法允许信息流在多条线上进行复制。多路径算法的优势是提高了数据吞吐率和可靠性。第第1111章章 路由算法与实验路由算法与实验 3) 平面和分层路由选择算法平面和分层路由选择算法

16、一些路由选择算法在平面空间运行，而另一些路由选择算法采用分层空间运行。在平面路由选择算法中，所有路由器是对等的，而在分层路由选择算法中，路由器被划分成主干路由器和非主干路由器。来自非主干路由器的数据包先被传送到主干路由器中，然后通过主干路由器转发到目的节点域，最后通过一个或多个非主干路由器到达目的节点。路由系统常将逻辑节点组称为域、自主系统或区域。在分层路由选择算法中，任一域中只有一部分路由器可以与其他域中的路由器通信，而其他路由器只能与该域中的路由器通信。在超大型的网络中，可能还存在更多的层次，一般都是位于最高层的路由器形成路由器的主干。第第1111章章 路由算法与实验路由算法与实验 分层路

17、由类似公司的组织结构，其主要优点是能较好地支持信息流模式。由于大多数网络通信发生在小公司群(域)中，且域内路由器只需要了解域内的其他路由器即可。因此，可以简化它们的路由选择算法，以相应地减少路由修正消息流发布。4) 主机智能和路由器智能路由选择算法主机智能和路由器智能路由选择算法一些路由选择算法假定源节点决定整个发送路由，这就是通常所说的源路由选择(source routing)。在源路由选择系统里，路由器只是一个存储和发送设备，负责向下一节点发送数据包。在这种系统中，主机具有路由选择的智能。第第1111章章 路由算法与实验路由算法与实验 而其他的算法假定主机对路由器一无所知，路由器根据自己计

18、算的结果来确定互联网上的路径。在这种系统中，路由器具有路由选择的智能。虽然主机智能路由选择算法在实际发送数据包之前就能发现到达目的节点的所有可能的路由，并能根据不同系统对最优路由的不同要求做出选择，但这种选择所有路径的方法常常需要耗费大量的时间。把主机智能路由选择算法与路由器智能路由选择算法结合起来使用是一种较好的方法。第第1111章章 路由算法与实验路由算法与实验 5) 域内和域间路由选择算法域内和域间路由选择算法一些路由选择算法只在域内运行，而另一些路由选择算法可在域内或域间运行。这两种算法在本质上存在不同。因此，一个最优的域内路由选择算法并不一定是最优的域间路由选择算法。第第1111章章

19、 路由算法与实验路由算法与实验 6) 链接状态和距离向量路由算法链接状态路由算法(也称作最短路径优先算法)将路由信息发送至互联网络的所有节点上，每个路由器只能传递描述其自身链接状态的那部分的路由表。而距离向量路由算法(也称作贝尔曼福特算法)要求每个路由器将路由表的全部或部分传送到与其相邻的路由器中。实际上，链接状态路由算法的更新消息只传送路由表更新的部分，而距离向量路由算法的更新消息将传送路由表的大部分或全部传送到与其相邻的路由器中。第第1111章章 路由算法与实验路由算法与实验 由于链接状态路由算法收敛速度较快，因此，它比距离向量路由选择算法更易避免路由循环。但由于链接状态路由算法需要占用更

20、多的CPU和内存资源，因此，它比距离向量路由算法更难以支持和实现。总的来说，这两种算法在大多数情况下运行良好。 3. 路由选择计量标准路由选择计量标准前面已经介绍过，路由表中包含软件选择的最佳路径的信息，但路由表是如何建立的呢？路由选择表中包含的信息是什么性质的呢？路由选择算法又是如何决定最优路由的呢？第第1111章章 路由算法与实验路由算法与实验 路由选择算法使用许多不同的计量标准确定最优路由，一些复杂的路由选择算法将多种计量标准融为一体。常用的计量标准有如下几种：(1) 路径长度。路径长度(path length)是最普通的一种计量标准。在路由选择协议允许网络管理员为每条网络链路分配任意权

21、值的情况下，路径长度是指所经过的每条链路的权值之和。而在路由选择协议定义了站点数目的情况下，路径长度是指数据包从源节点到目的节点过程中通过网络产品(如路由器)的数目。第第1111章章 路由算法与实验路由算法与实验 (2) 可靠性。可靠性(reliability)是指每个网络链路的可靠性(通常用比特-错误率描述)，即网络链路是否容易出现网络故障，一旦发生故障，是否能迅速修复。在进行可靠性等级分配时，应将考虑所有影响可靠性的因素。通常由网络管理员给网络链路分配可靠性等级，而这些等级一般用数值表示。(3) 路由选择延迟。路由选择延迟(routing delay)指的是通过互联网络从源节点发送数据包到

22、目标节点所需的时间。延迟时间取决于诸多因素，其中包括网络链路的带宽及网络堵塞程度、沿途每个路由器端口的队列和传输的物理距离等。由于延迟受几种重要因素的影响，因此，它是一种应用最广且最有用的计量标准。第第1111章章 路由算法与实验路由算法与实验 (4) 带宽。带宽(bandwidth)是指链路传输信息流的能力。在所有其他条件相同的情况下，10 Mb/s以太网链路显然优于64 kb/s的租用链路。尽管带宽越大表示链路的传输能力越强，但通过较大带宽链路的路由并不一定比通过较慢链路的路由更好，因为如果较快的链路非常繁忙，那么，通过它向目的节点传送数据包所需的实际时间可能会更长。(5) 负载。负载(l

23、oad)是指网络资源(如路由器)的繁忙程度，它可用多种方式进行计算，其中包括CPU的利用率和每秒处理数据包的次数。当然，持续不断地监控这些负载参数本身就要占用资源。第第1111章章 路由算法与实验路由算法与实验 (6) 通信开销。通信开销(communication cost)是另外一种重要的计量标准，尤其是当公司关心运行费用胜过运行性能时。对于这些公司来说他们宁可将数据包在自己的链路上进行传输(即使这样可能增加链路延迟)也不愿花钱(省时间)在公用链路上传输。4. 路由选择算法路由选择算法路由选择算法包括以下几种算法：Prim算法、Kruskal算法、Dijkstra算法、Floyd算法等。下

24、面依次介绍。第第1111章章 路由算法与实验路由算法与实验 11.1.6 图论基础知识图论基础知识1. 图的基本概念图的基本概念在介绍路由器算法之前，先介绍一些图论的基础知识。简单地说，图是一个包含了点和点间连线的集合。习惯上用G=(V，E)代表一个图，图中的节点又称顶点，V是节点的有穷(非空)集合，通常称节点的偶对为边，E是边的集合。图中代表一条边的节点偶对是无序的，则称此图为无向图。在无向图中(V1，V2)和(V2，V1)代表同一条边。如图11.1所示。第第1111章章 路由算法与实验路由算法与实验 图中代表一条边的节点偶对是有序的，则称此图为有向图。在有向图中，表示一条有向边，V1称为边

25、的始点，V2称为边的终点。和表示不同的边。如图11.2所示。第第1111章章 路由算法与实验路由算法与实验 adbc图11.1 无向图 第第1111章章 路由算法与实验路由算法与实验 adbc图11.2 有向图 第第1111章章 路由算法与实验路由算法与实验 图在实际应用时通常需要说明其他信息，这些信息可以附加到图的边或顶点上，用某种形式标识的图称为标号图。图11.3为标号图的两个例子。 第第1111章章 路由算法与实验路由算法与实验 adbcadbc318388926593141(a)(b)图11.3 标号图(a) 顶点带标号的有向图；(b) 边带标号的无向图第第1111章章 路由算法与实验

26、路由算法与实验 2. 图的表示法图的表示法有向图G=(V, E)，由于EVV，图中最多包含|V|2条边。对于给定顶点集V可能有个边集。因此，设计一个图的表示方法时，主要问题是如何适当的描述这个边集。假设有一个具有n个顶点的有向图G=(V，E)，Vv1，v2，vn。用一个nn阶的0-1矩阵A描述，即，即仅当vivj是G的一条边时，矩阵的第(i, j)个元素才为1。这个A矩阵称为相邻矩阵。第第1111章章 路由算法与实验路由算法与实验 图11.2所示的有向图的相邻矩阵为 。 相邻矩阵亦可描述无向图，由于(V1, V2)(V2, V1)，所以相邻矩阵是对称矩阵，且对角线上的元素都为0。图11.1所示

27、的无向图的相邻矩阵为 。1000100101000110A0100101101010110A第第1111章章 路由算法与实验路由算法与实验 把相邻矩阵加以变化，可以表示边带标号的图，把不存在的边对应的矩阵项设置为，其他值为标号图中的标识。例如图11.3所示的边带标号的无向图的相邻矩阵为2626594159314131A第第1111章章 路由算法与实验路由算法与实验 3. 图的实现图的实现我们把图看作是一类特殊的容器，在正规的情况下，图G=(V, E)是由两个集合(顶点集合和边集合)组成的序偶。在不正规情况下，图是一个有两个分隔仓的容器，一个为顶点，一个为边。因此存在三种对象，即顶点、边、图。相

28、应地，需要三个对象类：顶点类(Vertex)、边类(Edge)和图类(Graph)，如图11.4所示。第第1111章章 路由算法与实验路由算法与实验 ObjectEdgeWeightedEdgeWeightedVertexVertexContainerGraphOwnershipGraphAsMatrixGraphAsListsDigraphDigraphAsMatrixDigraphAsLists抽象类具体类图例:基类派生类图11.4 对象类层次 第第1111章章 路由算法与实验路由算法与实验 1) 顶点的实现顶点的实现在一个图中的各个顶点必须相互区别，即给顶点按顺序标号。类Vertex是从

29、基类Object中派生出来的，声明了单一成员变量number，对应于插入图中的每一个顶点的不同编号。第第1111章章 路由算法与实验路由算法与实验 class Vertex : public Objectpublic:typedef unsigned int Number;protected:Number number;public:Vertex(Number);Virtual operator Number () const;/;第第1111章章 路由算法与实验路由算法与实验 该程序定义了一个类Vertex的构造函数，这个构造函数只有一个赋给顶点编号的参数。另外，程序还声明了一个转换成编号的

30、成员函数operator Number，允许程序员在有整数的地方使用顶点，返回的是成员变量number的值。2) 边的实现边的实现在有向图中边是顶点的一个序偶，在无向图中边是一个含两个顶点的集合，由于概念的相似性，对它们使用相同的类，由边的具体使用来定义是有向边还是无向边。第第1111章章 路由算法与实验路由算法与实验 类Edge是从基类Object中派生出来的。class Edge: public Objectprotected:Vertex& v0;Vertex& v1;public:第第1111章章 路由算法与实验路由算法与实验 Edge(Vertext&,Ver

31、tex&);Virtual Vertex& V0 () const;Virtual Vertex& V1 () const;Virtual Vertex& Mate(Vertex const&) const;/; 类Edge包含两个变量v0和v1，分别为一个顶点的引用。当这类的实例用于描述一条有向边时，可表示v0v1。当这类的实例用于描述一条无向边时，可表示为v0, v1。程序声明了一个构造函数，带有两个参数，均为Vertex实例引用。这个构造函数的作用是对两个相应的成员变量进行初始化。第第1111章章 路由算法与实验路由算法与实验 除了构造函数，程序还

32、有三个公共成员函数：v0、v1、Mate，它们是访问者函数，前两个用于访问成员变量v0和v1。对于类Edge的任何实例e，Mate成员函数满足：e.Mate(e.v0()e.v1()e.Mate(e.v1()e.v0()因此如果知道顶点v是e的一个顶点，通过调用e.Mate(v)就能找到其他顶点。 第第1111章章 路由算法与实验路由算法与实验 3) 图的实现图的实现有向图和无向图有很多共同特点，因此在图类的实现中利用继承性似乎是顺理成章的。我们可以把有向图视作附有箭头的无向图。抽象类Graph和Digraph中，Graph是基类，描述无向图的具体类是由它派生的，Digraph拓宽了Graph

33、，描述有向图的具体类就是它派生的。第第1111章章 路由算法与实验路由算法与实验 class Graph : public Containerprotected:unsigned int numberOfVertices;unsigned int numberOfEdges;void DepthFirstTraversal(PrePostVistor&, Vertex&, Array&) const; public:第第1111章章 路由算法与实验路由算法与实验 Graph();virtual unsigned int numberOfEdges() const;vir

34、tual unsigned int numberOfVertices() const;virtual void AddVertex(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;第第1111章章 路由算

35、法与实验路由算法与实验 virtual bool IsEdge(Vertex:Number, Vertex:Number) const=0;virtual bool IsConnected() const;virtual bool IsCyclic() const;virtual Iterator& Vertices() const=0;virtual Iterator& Edges() const=0;virtual Iterator& IncidentEdges(Vertex const&) const=0;virtual Iterator& Ema

36、natingEdges(Vertex const&) const=0; virtual void DepthFirstTraversal(PrePostVisitor&, Vertex const&) const;第第1111章章 路由算法与实验路由算法与实验 virtual void BreadthFirstTraversal(Vistor&, Vertex const&) const;/; class Digraph : public virtual Graphpublic:virtual bool IsConnected() const;virtu

37、al bool IsCyclic() const;virtual void TopologicalOrderTraversal(Vistor&) const;第第1111章章 路由算法与实验路由算法与实验 Graph是一个包含了纯虚拟成员函数抽象类，并在从基类继承过来的成员变量中增加了两个新的成员变量numberOfVertices和numberOfEdges。Graph还声明了一个缺省的构造函数，这个构造函数的作用是把类的两个成员变量初始化为0。因此，最初图是空的既没有边也没有顶点。Graph类声明了下列存取器(accessor)和变更器(mutator)的成员函数：NumberOf

38、Edges：返回图包含的边的数量(存取器)。NumberOfVertices：返回图包含的顶点的数量(存取器)。AddVertex：把某个给定的顶点插入图中(变更器)。第第1111章章 路由算法与实验路由算法与实验 SelectVertex：带有一个整型参数，如i(0in)，并返回第i个顶点的引用(存取器)。operator：下标操作函数，带有一个整型值的下标表达式参数，其缺省操作是调用SelectVertex函数。AddEdge：把某个给定的边插入图中(变更器)。IsEdge：布尔型函数，带有两个Vertex:Number参数。如果图中有一条连接相应顶点的边，就返回true(存取器)。Sel

39、ectEdge：带有两个Vertex:Number参数。返回一个连接相应顶点的边的实例引用，当边不存在时，它的行为未定义。第第1111章章 路由算法与实验路由算法与实验 IsCyclic：如果图中有回路，返回true。IsConnect：如果图是连通的，返回true。下列每一个成员函数都将动态分配一个迭代器实例。(1) Vertices：类Graph的成员函数，返回一个遍历V中元素的迭代器。(2) Edges：类Graph的成员函数，返回一个遍历E中元素的迭代器。(3) IncidentEdge：这个成员函数带有一个指向顶点v的引用参数，返回一个遍历v的射入集中元素的迭代器。(4) Emana

40、tingEdges：这个成员函数带有一个指向顶点v的引用参数，返回一个遍历v的射出集中元素的迭代器。第第1111章章 路由算法与实验路由算法与实验 下列是Graph类中声明的图的遍历函数，作用是保证图中所有的顶点都将被系统访问。 (1) DepthFirstTraversal和BreadthFirstTraversal：这两个遍历函数带有两个参数，一个为Visitor对象的引用，另一个为顶点的引用。顶点规定了深度优先遍历或广度优先遍历的起始顶点。(2) TopologicalOrderTraversal：拓扑排序是对有向图节点所做的排序，拓扑排序遍历将按照拓扑排序规定的顺序来遍历图中的节点。因

41、此，它是类Digraph的一个成员函数。第第1111章章 路由算法与实验路由算法与实验 4) 无向图的实现无向图的实现类GraphAsMatrix是基类Graph的派生类，它用相邻矩阵描述图的边。由于类GraphAsMatrix是个具体类，所以必须提供基类中所有被定义为纯虚拟函数的具体实现，为简单起见，下面的程序删去了它的函数原型。class GraphAsMatrix：public virtual Graphprotected:Array vertices;Array2D adjacencyMatrix;public:GraphAsMatrix(unsigned int);/.;第第1111

42、章章 路由算法与实验路由算法与实验 类GraphAsMatrix的每一个实例都表示一个无向图，如 G ( V, E ) 。 它 的 两 个 成 员 变 量 v e r t i c e s 和adjacencyMatrix分别用于描述集合V和集合E。顶点集V用一个指向Vertex实例的一维指针数组描述，边集E用一个指向Edge实例的二维指针矩阵(数组)描述。GraphAsMatrix构造函数只有一个unsigned int类型的参数，这个参数规定了图可能包含的最大顶点数。它的值确定了顶点数组的长度及相邻矩阵的维度。第第1111章章 路由算法与实验路由算法与实验 4. 图的遍历图的遍历图有很多方面

43、的应用，因此有许多不同的算法来操纵它们，但是这些算法都必须能系统访问图中的所有节点(顶点)。即图的各种算法都要遍历图这种数据结构，并在每一个顶点处执行某种操作。这种遍历图的过程称为图的遍历(Graph Traversal)。常用的图的遍历有三种：深度优先遍历(Depth-first Traversal)、广度优先遍历(Breadth-first Traversal)和拓扑排序(Topological Sort)。这里只介绍前两种遍历方法。第第1111章章 路由算法与实验路由算法与实验 1) 深度优先遍历深度优先遍历图的深度优先遍历是访问一个顶点，然后递归的访问邻接于此节点的所有顶点。而问题在于

44、图可能有回路，并且遍历时访问每一个顶点的次数最多只能有一次，解决的方法是记录已访问过的节点，以使遍历不至于无限的递归进行。在图1.2中如果遍历从顶点c开始，则访问节点的顺序为：c、a、b、d。下面给出了两个深度优先遍历的子程序DepthFirstTraversal的实现代码。第一个是带两个参数的，这个子程序声明为public；另外一个带三个参数，这个子程序声明为protected。 第第1111章章 路由算法与实验路由算法与实验 void Graph:DepthFirstTraversal(prePostVisition& visitor, Vertex const& star

45、t) constArray visited(numberOfVertices); for(Vertex:Number v=0;vnumberOfVertices;+v)visitedv=false;DepthFirstTraversal(visitor, const_cast, (start)visited);第第1111章章 路由算法与实验路由算法与实验 void Graph:DepthFirstTraversal(prePostVisition& visitor,Vertex& vertex,Array& visited) constif(visitor.IsDon

46、e()return; visitor.PreVisit(vertex);visitedvertex=true;Iterator& p=EmanatingEdge(vertex);第第1111章章 路由算法与实验路由算法与实验 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);第第1

47、111章章 路由算法与实验路由算法与实验 2) 广度优先遍历广度优先遍历图的广度优先遍历首先访问深度为0的节点(根节点)，然后访问深度为1的节点，依此类推。所谓深度是指从起始顶点到给定顶点的最短路线长度。由于图没有根节点，必须确定遍历从哪个顶点开始。这样，广度优先遍历首先访问起始顶点，然后访问所有与起始顶点相邻的顶点，再访问所有与那些相邻顶点相邻的顶点，依此类推。图11.5是对图11.2所示的有向图进行广度优先遍历的过程。从顶点a开始的广度优先遍历访问的顺序为a、b、c、d。第第1111章章 路由算法与实验路由算法与实验 adbc开始ab,caabbcdccdd图11.5 广度优先遍历过程 第

48、第1111章章 路由算法与实验路由算法与实验 下面给出广度优先遍历子程序BreadthFirstTraversal的实现代码。有两个参数，分别指向Visitor实例的引用和指向Vertex实例的引用。void Graph: BreadthFirstTraversal(Visitor& visitor, Vertex const& start) constArray enqueued (numberOfVertices); for(Vertex:Number v=0;vnumberOfVertices;+v)Enqueuedv=false;第第1111章章 路由算法与实验路由算法

49、与实验 Queue& queue=*new QueueAsLinkedList(); queue.RescindOwnership();enqueuedstart=true;queue.Enqueue(const_cast(start);while(!queue.IsEmpty()&!visitor.IsDone()Vertex& vertex=dynamic_cast(queue.Dequeue();visitor.Visit(vertex);Iterator& p=EmanatingEdges(vertex);第第1111章章 路由算法与实验路由算法与实验

50、while(!p.IsDone()Edge& edge=dynamic_cast(*p);Vertex& to=edge.Mate(vertex);if(!enqueuedto)enqueuedto=ture;queue.Enqueue(to);第第1111章章 路由算法与实验路由算法与实验 +p;delete &p;delete &queue;第第1111章章 路由算法与实验路由算法与实验 11.2 Prim11.2 Prim算法算法 11.2.1 Prim算法原理算法原理 假设G(V, E)是一个具有n个顶点的边带权无向图，T(U，TE)是G的最小生成树，其

51、中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点(假定取v1)，将它并入U中，此时Uv1；然后只要U是V的真子集(即UV)，就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短(即权值最小)边，假定为(vi，vj)，其中viU，vjV-U，并把该边(vi，vj)和顶点vj分别并入T的边集TE和顶点集U；第第1111章章 路由算法与实验路由算法与实验 如此进行下去，每次往生成树里并入一个顶点和一条边，直到(n-1)次后就把所有n个顶点都并入到生成树T的顶点集中，此时UV，TE中含有(n-1)条边，T就是最后得到的最小生成树。第第1111

52、章章 路由算法与实验路由算法与实验 Prim算法的关键之处是：每次如何从生成树T中到T外的所有边中，找出一条最短边。例如，在第k次前，生成树T中已有k个顶点和(k-1)条边，此时T中到T外的所有边数为(k(n-k)，当然它包括两顶点间没有直接边相连，其权值被看作“无穷大”的边在内，从如此多的边中查找最短边，其时间复杂性为O(k(n-k)，显然是很费时的。是否有一种好的方法能够降低查找最短边的时间复杂性呢？回答是肯定的，它能够使查找最短边的时间复杂性降低到O(n-k)。 第第1111章章 路由算法与实验路由算法与实验 方法是：假定在进行第k次前已经保留着从T中到T外每一顶点(共(n-k)个顶点)

53、的各一条最短边，进行第k次时，首先从这(n-k)条最短边中，找出一条最最短的边(它就是从T中到T外的所有边中的最短边)，假设为(vi，vj)，此步需进行(n-k)次比较；然后把边(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)次运算做好了准备，此步需进行(n-k-1)次比较。

54、所以，利用此方法求第k次的最短边共需比较2(n-k)-1次，即时间复杂性为O(n-k)。第第1111章章 路由算法与实验路由算法与实验 例如，对于图11.6，它的邻接矩阵如图11.7所示。假定从v1出发利用Prim算法构造最小生成树T，在其过程中，每次向T中并入一个顶点和一条边后，顶点集U、边集TE(每条边的后面为该边的权)以及从T中到T外每个顶点的各一条最短边所构成的集合(假定用LW表示)的状态如下：初始态UvlTE LW(v1, v2)8, (v1, v3), (v1, v4)5, (v1, v5), (v1, v6) , (v1, v7)第第1111章章 路由算法与实验路由算法与实验 第

55、一次 Uvl, v4 TE(v1, v4)5 LW(v4, v2)3, (v1, v3), (v1, v4)5, (v4, v6)7, (v4, v7)15第二次 Uvl, v4, v2TE(v1, v4)5 , v4, v2)3LW(v2, v3)12, (v2, v5)10, (v4, v6)7, (v4, v7)15第第1111章章 路由算法与实验路由算法与实验 第五次 Uvl, v4, v2, v6, v3, v5TE(v1, v4)5 , v4, v2)3, (v4, v6)7, (v6, v3)2, (v3, v5)6LW(v4, v7)15第六次 Uvl, v4, v2, v6,

56、 v3, v5, v7TE(v1, v4)5 , (v4, v2)3, (v4, v6)7, (v6, v3)2, (v3, v5)6, (v4, v7)15LW 第第1111章章 路由算法与实验路由算法与实验 12465378351210692715图11.6 图形说明 第第1111章章 路由算法与实验路由算法与实验 1234567858123101262537151069279151234567图11.7 图11.6的邻接矩阵 第第1111章章 路由算法与实验路由算法与实验 每次对应的图形如图11.8中(a)(g)所示。实线表示TE集合中的边，虚线表示LW集合中的边。图11.8(g)就是最

57、后得到的最小生成树。第第1111章章 路由算法与实验路由算法与实验 124356785(a)124356753715(b)12435675310127(c)12435675392715(d)12435675362715(e)12435675362715(f)12435675362715(g)15图11.8 Prim算法的运行过程 第第1111章章 路由算法与实验路由算法与实验 11.2.2 Prim算法实现算法实现函数PrimAlogrithm有两个参数，第一个参数是一个指向无向图实例的const型引用，这个无向图是一个边带权的图，且权是int类型。第二个参数也是const类型引用，是一个指向

58、起始点(顶点)的引用。函数返回一棵用无向图描述的最小支撑树，即一个Graph实例的引用。Graph& PrimAlgorithm (Graph const& g，Vertex const& s)unsigned int const n=g.NumberOfVertices();Arraytable(n); PriorityQueue& queue=*new BinaryHeap (g.NumberOfEdges();第第1111章章 路由算法与实验路由算法与实验 tables.distance=0;q u e u e . E n q u e u e ( * n

59、e w A s s o c ( 0 , const_cast(s);while(!queue.IsEmpty()Assoc& assoc=dynamic_cast(queue.DequeueMin();Vertex& v0= dynamic_cast(assoc.Value();if(!tablev0.known)第第1111章章 路由算法与实验路由算法与实验 tablev1.distance=d;tablev1.predecessor=v0;queue.Enqueue(*new Assoc(d,v1);+p;delete &p;第第1111章章 路由算法与实验路由算法

60、与实验 delete &assoc;delete &queue;Graph& result=*new GraphAsLists(n);for (Vertex:Number v=0; vn; +v)result.AddVertex(*new Vertex(v);for (Vertex:Number v=0; vn; +v)if(v!=s)r e s u l t . A d d E d g e ( * n e w E d g e ( r e s u l t v , resulttablev.predecessor); return result;第第1111章章 路由算法与实验路由算法与实验 11.3 Kruskal算法算法 11.3.1 Kruskal算法原理算法原理 假设G(V, E)是一个具有n个顶点的边带权无向图，T(U, TE)是G的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空。此算法的基本思想是：将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留为T的一条边，若选取的边使生成树T形成回路，则将其舍弃，如此进行下去，直到TE中包含有n-1条边为止，此时的T即为最小生成树。图11.9是边带权无向图，图11.10是K