第7章数据结构中的图.ppt

《第7章数据结构中的图.ppt》由会员分享，可在线阅读，更多相关《第7章数据结构中的图.ppt（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与应用数据结构与应用马石安马石安 魏文平魏文平 编著编著1内容简介内容简介 本教材采用本教材采用本教材采用本教材采用面向对象面向对象面向对象面向对象的观点讨论数据结构技术，并以的观点讨论数据结构技术，并以的观点讨论数据结构技术，并以的观点讨论数据结构技术，并以C+C+C+C+类模板类模板类模板类模板作为算法描述工具。作为算法描述工具。作为算法描述工具。作为算法描述工具。教材在简要回顾教材在简要回顾教材在简要回顾教材在简要回顾C+C+C+C+程序设计概念的基础上，全面系统程序设计概念的基础上，全面系统程序设计概念的基础上，全面系统程序设计概念的基础上，全面系统地介绍了地介绍了地介绍了地介

2、绍了线性表、栈和队列、串、数组和广义表、树线性表、栈和队列、串、数组和广义表、树线性表、栈和队列、串、数组和广义表、树线性表、栈和队列、串、数组和广义表、树和二叉树及图和二叉树及图和二叉树及图和二叉树及图等数据结构，讨论了常用的等数据结构，讨论了常用的等数据结构，讨论了常用的等数据结构，讨论了常用的查找和排序查找和排序查找和排序查找和排序技术，对每一种数据结构，除了详细阐述其逻辑结构、技术，对每一种数据结构，除了详细阐述其逻辑结构、技术，对每一种数据结构，除了详细阐述其逻辑结构、技术，对每一种数据结构，除了详细阐述其逻辑结构、存储结构和相关算法外，还对所有算法进行了存储结构和相关算法外，还对所

3、有算法进行了存储结构和相关算法外，还对所有算法进行了存储结构和相关算法外，还对所有算法进行了C+C+C+C+语言语言语言语言实现和评价，并给出了应用实例。实现和评价，并给出了应用实例。实现和评价，并给出了应用实例。实现和评价，并给出了应用实例。教材附录给出了上机实验内容。教材附录给出了上机实验内容。教材附录给出了上机实验内容。教材附录给出了上机实验内容。2教材目录教材目录第第第第0 0 0 0章章章章 C+C+C+C+程序设计语言预备知识程序设计语言预备知识程序设计语言预备知识程序设计语言预备知识0.1 0.1 0.1 0.1 一个简单一个简单一个简单一个简单C+C+C+C+语言程序语言程序语

4、言程序语言程序0.2 0.2 0.2 0.2 指针与引用指针与引用指针与引用指针与引用0.3 0.3 0.3 0.3 动态存贮分配动态存贮分配动态存贮分配动态存贮分配0.4 0.4 0.4 0.4 函数函数函数函数0.5 0.5 0.5 0.5 类与对象类与对象类与对象类与对象0.6 0.6 0.6 0.6 运算符重载运算符重载运算符重载运算符重载0.7 0.7 0.7 0.7 模板模板模板模板3第第第第1 1 1 1章章章章 绪论绪论绪论绪论1.1 1.1 1.1 1.1 数据结构的产生和发展数据结构的产生和发展数据结构的产生和发展数据结构的产生和发展1.2 1.2 1.2 1.2 数据结构

5、研究的内容数据结构研究的内容数据结构研究的内容数据结构研究的内容1.3 1.3 1.3 1.3 基本概念和术语基本概念和术语基本概念和术语基本概念和术语1.4 1.4 1.4 1.4 算法算法算法算法第第第第2 2 2 2章线性表章线性表章线性表章线性表2.1 2.1 2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构2.2 2.2 2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构2.3 2.3 2.3 2.3 线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构2.4 2.4 2.4 2

6、.4 顺序表和链表的比较顺序表和链表的比较顺序表和链表的比较顺序表和链表的比较2.5 2.5 2.5 2.5 线性表的应用线性表的应用线性表的应用线性表的应用4第章栈和队列第章栈和队列第章栈和队列第章栈和队列3.1 3.1 3.1 3.1 栈栈栈栈3.2 3.2 3.2 3.2 队列队列队列队列3.3 3.3 3.3 3.3 栈的应用栈的应用栈的应用栈的应用第第第第4 4 4 4章章章章 串串串串4.1 4.1 4.1 4.1 串的逻辑结构串的逻辑结构串的逻辑结构串的逻辑结构4.2 4.2 4.2 4.2 串的顺序存储结构串的顺序存储结构串的顺序存储结构串的顺序存储结构4.3 4.3 4.3

7、4.3 串的链式存储结构串的链式存储结构串的链式存储结构串的链式存储结构4.4 4.4 4.4 4.4 串的应用串的应用串的应用串的应用 5第第第第5 5 5 5章章章章 数组和广义表数组和广义表数组和广义表数组和广义表5.1 5.1 5.1 5.1 数组数组数组数组5.2 5.2 5.2 5.2 矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储矩阵的压缩存储5.3 5.3 5.3 5.3 广义表广义表广义表广义表5.4 5.4 5.4 5.4 多维数组的应用多维数组的应用多维数组的应用多维数组的应用6第第第第6 6 6 6章章章章 树和二叉树树和二叉树树和二叉树树和二叉树6.1 6.1 6.1 6

8、.1 树的逻辑结构树的逻辑结构树的逻辑结构树的逻辑结构6.2 6.2 6.2 6.2 树的顺序存储结构树的顺序存储结构树的顺序存储结构树的顺序存储结构6.3 6.3 6.3 6.3 二叉树的逻辑结构二叉树的逻辑结构二叉树的逻辑结构二叉树的逻辑结构6.4 6.4 6.4 6.4 二叉树的存储结构二叉树的存储结构二叉树的存储结构二叉树的存储结构6.5 6.5 6.5 6.5 线索二叉树线索二叉树线索二叉树线索二叉树6.6 6.6 6.6 6.6 树、森林与二叉树的转换树、森林与二叉树的转换树、森林与二叉树的转换树、森林与二叉树的转换6.7 6.7 6.7 6.7 树的应用树的应用树的应用树的应用7

9、第第第第7 7 7 7章章章章 图图图图7.1 7.1 7.1 7.1 图的逻辑结构图的逻辑结构图的逻辑结构图的逻辑结构7.2 7.2 7.2 7.2 图的存储结构图的存储结构图的存储结构图的存储结构7.3 7.3 7.3 7.3 图的遍历图的遍历图的遍历图的遍历7.4 7.4 7.4 7.4 生成树和最小生成树生成树和最小生成树生成树和最小生成树生成树和最小生成树7.5 7.5 7.5 7.5 最短路径最短路径最短路径最短路径7.6 DAG7.6 DAG7.6 DAG7.6 DAG图及其应用图及其应用图及其应用图及其应用8第第第第8 8 8 8章章章章 排序排序排序排序8.1 8.1 8.1

10、 8.1 概述概述概述概述8.2 8.2 8.2 8.2 插入排序插入排序插入排序插入排序8.3 8.3 8.3 8.3 交换排序交换排序交换排序交换排序8.4 8.4 8.4 8.4 选择排序选择排序选择排序选择排序8.5 8.5 8.5 8.5 归并排序归并排序归并排序归并排序8.6 8.6 8.6 8.6 基数排序基数排序基数排序基数排序8.7 8.7 8.7 8.7 各种内排序方法的比较和选择各种内排序方法的比较和选择各种内排序方法的比较和选择各种内排序方法的比较和选择9第第第第9 9 9 9章章章章 查找查找查找查找9.1 9.1 9.1 9.1 概述概述概述概述9.2 9.2 9.

11、2 9.2 线性表的查找线性表的查找线性表的查找线性表的查找9.3 9.3 9.3 9.3 树表的查找树表的查找树表的查找树表的查找9.4 9.4 9.4 9.4 散列表的查找散列表的查找散列表的查找散列表的查找附录附录附录附录 实验内容实验内容实验内容实验内容10第第7 7章章 图图117 7.1.1 图的逻辑结构图的逻辑结构7 7.2.2 图的存储结构图的存储结构图的存储结构图的存储结构7 7.3.3 图的遍历图的遍历图的遍历图的遍历本章主要内容本章主要内容7 7.4.4 生成树和最小生成树生成树和最小生成树生成树和最小生成树生成树和最小生成树7 7.5.5 最短路径最短路径最短路径最短路

12、径7 7.6.6 DAGDAGDAGDAG图及其应用图及其应用图及其应用图及其应用127.1.17.1.1图的定义图的定义7.1 7.1 图的逻辑结构图的逻辑结构图图G G由由结结点点的的有有穷穷非非空空集集合合V V和和边边的的有有穷穷集集合合E E组组成成，记记为为G=(VG=(V，E)E)。在在图图结结构构中中，将将结结点点称称为为顶顶点点，以以便便与与树树形形结结构构加加以以区区别别，边边则则是是顶顶点点的的偶偶对对，若若两两个个顶顶点点之之间间存存在在一一条条边边，就就表表示示这这两两个个顶顶点点具具有有相相邻邻关关系系。通通常常，也也将将图图G G的的顶顶点点集集和和边边集集分分别

13、别记记为为V(G)V(G)和和E(G)E(G)。E(G)E(G)可可以以是是空空集集，若若E(G)E(G)为为空空，则则图图G G只有顶点而没有边。只有顶点而没有边。137.1.2 7.1.2 图的基本术语图的基本术语 1.1.有向图和无向图有向图和无向图 如如果果G G中中的的每每条条边边都都是是有有方方向向的的，则则称称G G为为有向图有向图。在在有有向向图图中中，一一条条有有向向边边是是由由两两个个顶顶点点组组成的有序对，通常成的有序对，通常用尖括号表示用尖括号表示。例例如如，表表示示一一条条有有向向边边，vivi是是边边的的始点，始点，vjvj是边的终点。是边的终点。14若若图图G G

14、中中的的每每条条边边都都是是没没有有方方向向的的，则则称称G G为为无向图。无向图。无无向向图图中中的的边边均均是是顶顶点点的的无无序序对对，通通常常用用圆圆括括号号表表示示。无无序序对对(vi,vjvi,vj)和和(vj,vivj,vi)表表示示同同一条边。一条边。15无向图无向图G1G1，在该图中：，在该图中：V(G1)=v1V(G1)=v1，v2v2，v3v3，v4v4，v5v5E(G1)=(v1,v2)E(G1)=(v1,v2)，(v1,v4)(v1,v4)，(v2,v3)(v2,v3)，(v2,v5)(v2,v5)，(v3,v4)(v3,v4)，(v3,v5)(v3,v5)16有向图

15、有向图G2G2，该图的顶点集和边集分别为：，该图的顶点集和边集分别为：V(G2)=v1V(G2)=v1，v2v2，v3v3，v4v4，v5v5E(G2)E(G2)，172.2.稠密图和稀疏图稠密图和稀疏图 3.3.边和顶点的关系边和顶点的关系 若若(vi,vj)是是一一条条无无向向边边，则则称称顶顶点点vi和和vj互互为为邻邻接接点点(adjacent)，或或称称vi和和vj相相邻邻接接，并并称称(vi,vj)依依附附或或关关联联(incident)于于顶顶点点vi和和vj或或称称(vi,vj)与与顶顶点点vi和和vj相关联。相关联。若若是是一一条条有有向向边边，则则称称此此边边是是顶顶点点v

16、i的的一一条条出出边边，同同时时也也是是顶顶点点vj的的一一条条入入边边；称称顶顶点点vi邻邻接接到到(或或邻邻接接于于)顶顶点点vj，并并称称边边关关联联于于vi和和vj，或称，或称与顶点与顶点vi和和vj相关联。相关联。184.4.顶点的度顶点的度 无无向向图图中中顶顶点点v v的的度度是是关关联联于于该该顶顶点点的的边边的的数数目，记为目，记为D(vD(v)。在在有有向向图图中中，以以顶顶点点v v为为终终点点的的边边的的数数目目称称为为v v的的入入度度，记记为为ID(vID(v)；以以顶顶点点v v为为始始点点的的边边的的数数目目称称为为v v的的出出度度，记记为为OD(vOD(v)

17、。顶顶点点v v的的度度定定义义 为为 该该 顶顶 点点 的的 入入 度度 和和 出出 度度 之之 和和，即即D(vD(v)=)=ID(v)+OD(vID(v)+OD(v)。195.5.子图子图 设设G=(V，E)是是一一个个图图，若若V 是是V的的子子集集，E 是是E的的子子集集，且且E 的的边边所所关关联联的的顶顶点点均均在在V 中中，则则G=(V，E)也也是是一一个个图图，并并称称其其为为G的子图。的子图。206.6.路径路径 设设G是是图图，若若存存在在一一个个顶顶点点序序列列vp，v1，v2，vq-1，vq使使得得(vp,v1)，(v1,v2)，(vq-1,vq)属属于于E，则则称称

18、vp到到vq存存在在一一条条路路径径(path)，其中，其中vp为起点，为起点，vq为终点。为终点。路径的长度是该路径上边的数目。路径的长度是该路径上边的数目。217.7.有根图和图的根有根图和图的根 8.8.无向图的连通图和连通分量无向图的连通图和连通分量 9.9.有向图的强连通图和强连通分量有向图的强连通图和强连通分量 10.10.网络网络 227.1.3 7.1.3 图的基本操作图的基本操作 图的基本操作图的基本操作:图的初始化：图的初始化：Create()Create()销毁图：销毁图：DestoryDestory()()删除图中所有元素，回收图所占空间。删除图中所有元素，回收图所占空

19、间。取顶点：取顶点：GetVex(iGetVex(i)取图中的第取图中的第i i 个顶点的数据信息。个顶点的数据信息。23 插入顶点：插入顶点：InsertVex(vInsertVex(v)在图中插入顶点在图中插入顶点v v。删除顶点：删除顶点：DeleteVex(vDeleteVex(v)删除图中顶点删除图中顶点v v。插入边或弧：插入边或弧：Insert(v,wInsert(v,w)在在图图中中插插入入一一条条边边(v,wv,w)或或弧弧 ，如如是是无无向图，还应增加对称边向图，还应增加对称边(w,v)(w,v)。删除边或弧：删除边或弧：Delete(v,wDelete(v,w)247.2

20、 7.2 图的存储结构图的存储结构 图图的的存存储储表表示示方方法法很很多多，邻邻接接矩矩阵阵表表示示法法和和邻邻接表表示法接表表示法是两种最常用的方法。是两种最常用的方法。7.2.17.2.1邻接矩阵邻接矩阵 邻邻接接矩矩阵阵是是一一种种表表示示顶顶点点之之间间相相邻邻关关系系的的矩矩阵阵。设设G=(VG=(V，E)E)是是具具有有n n个个顶顶点点的的图图，则则G G的的邻接矩阵邻接矩阵A A是具有如下性质的是具有如下性质的n n阶方阵：阶方阵：25对对于于无无向向图图，若若从从顶顶点点vivi到到vjvj有有一一条条无无向向边边(vi,vjvi,vj)，则则 aijaij=1=1，aji

21、aji=1;=1;否否 则则aijaij=0=0，ajiaji=0=0，故故无无向向图图的的邻邻接接矩矩阵阵是是一一个个对对称称矩矩阵阵。对对于于有有向向图图，若若从从顶顶点点vivi到到vjvj有有一一条条有有向向边边 j，则则aijaij=1=1；否否则则aijaij=0=0。262728基于邻接矩阵存储结构的图的类模板定义基于邻接矩阵存储结构的图的类模板定义cx7_1.h cx7_1.h 29邻接矩阵的基本操作及其实现邻接矩阵的基本操作及其实现:1 1求顶点在图中的位置求顶点在图中的位置 2 2创建图创建图 3 3顶点的增删顶点的增删 4 4弧的增删弧的增删 5 5输出邻接矩阵输出邻接矩

22、阵 6 6销毁有向图销毁有向图 307.2.2 7.2.2 邻接表邻接表 邻邻接接表表表表示示法法是是图图的的一一种种链链接接存存储储结结构构，类类似似于于树树的的孩子链表表示法。孩子链表表示法。对对于于图图G G中中的的每每个个顶顶点点vivi，该该方方法法把把所所有有邻邻接接于于vivi的的顶顶点点链链成成一一个个单单链链表表，这这个个单单链链表表就就称称为为顶顶点点vivi的的邻邻接接表表，邻邻接接表表中中每每个个结结点点有有两两个个域域：其其一一是是邻邻接接点点域域(adjvexadjvex)，用用以以存存放放与与vivi相相邻邻接接的的顶顶点点vjvj的的序序号号j j；其其二二是是

23、链链域域(next)(next)，用用来来指指示示与与vivi相相邻邻接接的的下下一一顶顶点点，从而将邻接表的所有表结点链在一起。从而将邻接表的所有表结点链在一起。31为为每每个个顶顶点点vivi的的邻邻接接表表设设置置一一个个头头结结点点，头头结结点点中中包包含含两两个个域域，其其中中一一个个是是顶顶点点域域vertexvertex，用用来来存存放放顶顶点点vivi的的数数据据信信息息；另另一一个个是是指指针针域域firstedgefirstedge，它它指指向向vivi的的邻邻接接表表的的开开始始结结点点，相相当当于于vivi的的邻邻接接表表的的头头指指针针。为为了了便便于于随随机机访访问

24、问任任一一顶顶点点的的邻邻接接表表，将将所所有有头头结结点点顺顺序序存存储储在在一一个个一一维维数数组组中中，称称为为顶顶点点表表，将将其其中中的的头头结结点点称称为为顶顶点点表表结结点点。这这样样就就构构成成了了图图的的邻邻接接表表表示。表示。323334邻接表的基本操作及其实现邻接表的基本操作及其实现:求顶点在图中的位置求顶点在图中的位置 创建有向图创建有向图 顶点的增删顶点的增删 弧的增删弧的增删 输出邻接表输出邻接表 销毁有向图销毁有向图 357.2.3 7.2.3 邻接矩阵和邻接表的比较邻接矩阵和邻接表的比较 367.3 7.3 图的遍历图的遍历 图图的的遍遍历历是是指指从从图图中中

25、某某一一顶顶点点出出发发，对对图图中中所所有顶点访问一次且仅访问一次的操作。有顶点访问一次且仅访问一次的操作。377.3.1 7.3.1 深度优先搜索遍历深度优先搜索遍历 深深度度优优先先搜搜索索(DFS)(DFS)遍遍历历类类似似于于树树的的先先序序遍遍历历。假假定定给给定定图图G G的的初初态态是是所所有有顶顶点点均均未未曾曾访访问问过过。则则从从图图中中某某顶顶点点v v出出发发进进行行深深度度优优先先搜搜索索遍遍历历的基本思想是：的基本思想是：(1)(1)访问顶点访问顶点v v；(2)(2)从从v v的的未未被被访访问问的的邻邻接接点点中中选选取取一一个个顶顶点点w w，从，从w w出

26、发进行深度优先搜索遍历；出发进行深度优先搜索遍历；(3)(3)重重复复上上述述两两步步，直直至至图图中中所所有有和和v v有有路路径相通的顶点都被访问到。径相通的顶点都被访问到。38从从图图中中某某顶顶点点v v出出发发，基基于于邻邻接接矩矩阵阵表表示示的的深深度度优先搜索的递归过程如程序优先搜索的递归过程如程序sf7_13.cppsf7_13.cpp所示。所示。从从图图中中某某顶顶点点v v出出发发，基基于于邻邻接接表表表表示示的的深深度度优优先搜索的递归过程如程序先搜索的递归过程如程序sf7_15.cppsf7_15.cpp所示。所示。39无向图无向图G12G12和它的深度优先搜索遍历和它

27、的深度优先搜索遍历:得到的顶点访问序列为：得到的顶点访问序列为：v0 v1 v2 v5 v4 v6 v3 v7 v0 v1 v2 v5 v4 v6 v3 v7 407.3.2 7.3.2 广度优先搜索遍历广度优先搜索遍历 广广度度优优先先搜搜索索 (breadth(breadth first first serchserch，BFS)BFS)遍遍历历类类似于树的层序遍历。似于树的层序遍历。从图中某顶点从图中某顶点v v出发进行广度优先遍历的基本思想是：出发进行广度优先遍历的基本思想是：(1)(1)访问顶点访问顶点v v；(2)(2)依依次次访访问问v v的的各各个个未未被被访访问问的的邻邻接接

28、点点v1v1，v2v2，vkvk；(3)(3)分分别别从从v1v1，v2v2，vkvk出出发发依依次次访访问问它它们们未未被被访访问问的的邻邻接接点点，并并使使“先先被被访访问问顶顶点点的的邻邻接接点点”先先于于“后后被被访访问问顶顶点点的的邻邻接接点点”被被访访问问，直直至至图图中中所所有有与与顶顶点点v v有路径相通的顶点都被访问到。有路径相通的顶点都被访问到。41无向图无向图G12G12的广度优先搜索遍历的广度优先搜索遍历:v0 v1 v3 v4 v2 v6 v5 v7v0 v1 v3 v4 v2 v6 v5 v7427.4 7.4 生成树和最小生成树生成树和最小生成树 在在图图论论中中

29、，常常常常将将一一个个无无回回路路的的连连通通图图定定义义为为树树。没有确定谁是根的图称为。没有确定谁是根的图称为自由树自由树。7.4.1 7.4.1 生成树与生成森林生成树与生成森林 如如果果连连通通图图G G的的一一个个子子图图是是一一棵棵包包含含G G中中所所有有顶顶点的树，则该子图称为点的树，则该子图称为G G的生成树。的生成树。43由由深深度度优优先先搜搜索索得得到到的的生生成成树树称称为为深深度度优优先先生生成树成树，简称为，简称为DFSDFS生成树；生成树；由由广广度度优优先先搜搜索索得得到到的的生生成成树树称称为为广广度度优优先先生生成树成树，简称为，简称为BFSBFS生成树。

30、生成树。4445图图的的生生成成树树不不唯唯一一。从从不不同同的的顶顶点点出出发发进进行行遍遍历，可以得到不同的生成树。历，可以得到不同的生成树。467.4.2 7.4.2 最小生成树最小生成树 带带权权的的连连通通图图也也称称连连通通网网，其其生生成成树树也也是是带带权权的的，我我们们把把生生成成树树各各边边的的权权值值总总和和称称为为该该生成树的权。生成树的权。图图的的生生成成树树不不唯唯一一，从从不不同同的的顶顶点点出出发发遍遍历历带带权权的的连连通通图图，可可以以得得到到不不同同的的带带权权生生成成树树，其其中中权权值值最最小小的的生生成成树树称称为为最最小小生生成成树树，简简称为称为

31、MSTMST。47普普里里姆姆(Prim)(Prim)算算法法和和克克鲁鲁斯斯卡卡尔尔(KruskalKruskal)算算法法是是两个利用两个利用MSTMST性质构造最小生成树的算法。性质构造最小生成树的算法。1 1普里姆算法普里姆算法 假假设设G=(V,E)是是连连通通网网络络，TE是是G上上最最小小生生成成树树中中边边的的集集合合。算算法法从从V中中任任取取一一个个顶顶点点作作为为源源点点(假假定定为为v0)，此此时时U=v0(v0V)，TE开开始始，重重复复执执行行下下述述操操作作：在在所所有有uU，vV-U的的边边(u，v)E中中找找一一条条代代价价最最小小的的边边(u，v)并并入入集

32、集合合TE，同同时时u并并入入U，直直至至UV为为止止。此此时时TE中必有中必有n-1条边，则条边，则T(V，TE)为为G的最小生成树。的最小生成树。4849505152采用邻接矩阵存储的采用邻接矩阵存储的PrimPrim算法算法sf7_20.cpp sf7_20.cpp 532 2克鲁斯卡尔算法克鲁斯卡尔算法 假假设设连连通通网网G G(V(V，E)E)，则则令令最最小小生生成成树树的的初初始始状状态态为为只只有有n n个个顶顶点点而而无无边边的的非非连连通通图图T=(VT=(V，)，图图中中每每个个顶顶点点自自成成一一个个连连通通分分量量。在在E E中中选选择择权权值值最最小小的的边边，若

33、若该该边边依依附附的的顶顶点点落落在在T T中中不不同同的的连连通通分分量量上上，则则将将此此边边加加入入到到T T中中，否否则则舍舍去去此此边边而而选选择择下下一一条条权权值值最最小小的的边边。依依次次类类推推，直直至至T T中中所所有有顶顶点点都都在在同同一一连连通分量上为止。通分量上为止。54555657克鲁斯卡尔算法克鲁斯卡尔算法sf7_21.cppsf7_21.cpp587.5 7.5 最短路径最短路径 7.5.1 7.5.1 单源最短路径单源最短路径 所所谓谓单单源源最最短短路路径径：是是指指对对已已知知图图G=(VG=(V，E)E)，给定源顶点给定源顶点v v，找出，找出v v到

34、其余各顶点的最短路径。到其余各顶点的最短路径。591.1.迪杰斯特拉迪杰斯特拉(DjikstraDjikstra)算法基本思想算法基本思想 迪迪杰杰斯斯特特拉拉提提出出了了按按路路径径长长度度递递增增的的次次序序逐逐一一产产生最短路径的算法：生最短路径的算法：首首先先求求得得长长度度最最短短的的一一条条最最短短路路径径，再再求求得得长长度度次次短短的的一一条条最最短短路路径径，依依此此类类推推，直直到到从从源源点点到到其它所有顶点之间的最短路径都已求得为止。其它所有顶点之间的最短路径都已求得为止。60设设集集合合S存存放放已已经经求求得得最最短短路路径径的的终终点点，则则V-S为为尚尚未未求求

35、得得最最短短路路径径的的终终点点。初初始始状状态态时时，集集合合S中中只只有有一一个个源源点点，设设为为顶顶点点v0。迪迪杰杰斯斯特特拉拉算算法法的的具具体体做做法法是是：首首先先产产生生从从点点v0到到自自身身的的路路径径，其其长长度度为为0，将将v0加加入入S；算算法法的的每每一一步步上上，按按照照最最短短路路径径值值的的递递增增次次序序，产产生生下下一一条条最最短短路路径径，并并将将该该路路径径的的终终点点vjV-S加加入入S；直到直到S=V，算法结束。，算法结束。612.2.算法描述算法描述 623.3.算法实现算法实现 教材教材sf7_22.cppsf7_22.cpp637.5.27

36、.5.2所有顶点对之间的最短路径所有顶点对之间的最短路径 1.1.弗洛伊德算法思想弗洛伊德算法思想 求求从从顶顶点点vi到到 vj的的最最短短路路径径。设设集集合合S的的初初始始状状态态为为空空集集合合。然然后后，依依此此向向集集合合S中中加加入入顶顶点点v0，v1，v2vn-1，每每次次加加入入一一个个顶顶点点。用用二二维维数数组组dist保保存存各各条条最最短短路路径径的的长长度度，其其中中，distij为为从从i到到j的的当当前前最最短短路路径径长长度度。随随着着S中中的的顶顶点点的的不不断断增增加加，distij的的值值不不断断修修正正，当当S=V时时，distij的的值值就就是从是从

37、i到到j的最短路径。的最短路径。642.2.算法描述算法描述 图图7.24 7.24 用用弗弗洛洛伊伊德德算算法法求求带带权权有有向网所有顶点对的最短路径向网所有顶点对的最短路径 653.3.算法实现算法实现 教材教材sf7_23.cpp sf7_23.cpp 667.6 DAG7.6 DAG图及其应用图及其应用 一一个个无无环环的的有有向向图图称称作作有有向向无无环环图图，简简称称DAGDAG图图。DAGDAG图是一类比有向树更一般的特殊有向图。图是一类比有向树更一般的特殊有向图。677.6.2 AOV7.6.2 AOV网与拓扑排序网与拓扑排序 1 1AOVAOV网网 以以有有向向图图中中的

38、的顶顶点点表表示示活活动动，弧弧表表示示活活动动之之间间的的优优先先关关系系，这这样样的的有有向向图图称称为为顶顶点点表表示示活活动动的网，简称的网，简称AOVAOV网。网。682 2拓扑排序拓扑排序 设设G=(V,E)G=(V,E)是是一一个个具具有有n n个个顶顶点点的的有有向向图图，V V中中的的顶顶点点序序列列v0v0，v1v1，vn-1vn-1称称为为一一个个拓拓扑扑序序列列，当当且且仅仅当当满满足足下下列列条条件件：若若从从vivi到到顶顶点点vjvj有有一一条条路路径径，则则在在顶顶点点序序列列中中顶顶点点vivi必必在在顶顶点点vjvj之之前前。对对一一个个有有向向图图构构造造

39、拓拓扑扑序序列的过程称为拓扑排序。列的过程称为拓扑排序。693 3拓扑排序的实现拓扑排序的实现 教材教材sf7_24.cpp sf7_24.cpp 707.6.3 AOE7.6.3 AOE网与关键路径网与关键路径 1.AOE1.AOE网网与与AOVAOV网网对对应应的的是是AOE(ActivityAOE(Activity On On Edge)Edge)网网，即即边边表表示示活活动动的的网网。在在AOVAOV网网中中，有有向向图图的的顶顶点点表表示示一一项项任任务务，有有向向边边表表示示任任务务之之间间的的先先后后关关系系。在在实实际际应应用用中中，任任务务之之间间除除了了先先后后关关系系外外，还还有有时时间间上上的的约约束束，用用AOEAOE网网来来表表示示这这种种约束关系。约束关系。712关键路径关键路径在在AOE网网中中，因因为为有有些些活活动动可可以以同同时时进进行行，所所以以完完成成一一个个工工程程所所需需的的最最短短时时间间是是从从一一个个始始点点到到一一个个终终点点的的最最大大路路径径长长度度。具具有有最最大大长长度度的路径被称为关键路径的路径被称为关键路径(critical path)。723 3关键路径的确定关键路径的确定 教材教材sf7_25.cpp sf7_25.cpp 737475