第6章图—数据结构

1、 数据结构励志照亮人生 编程改变命运1第第6 6章章 图图的结构分析与应用的结构分析与应用 学习目标学习目标 了解图的定义及基本术语。 熟练掌握图的邻接矩阵和邻接链表存储方法。 熟练掌握图的深度优先和广度优先遍历。 熟练掌握最小生成树实现方法：普里姆算法(Prim)和克 鲁斯卡尔(Kruskal)算法。 掌握求单源最短路径的迪杰斯特拉(Dijkstra)算法，了解 求每对顶点间最短路径的弗洛伊德(Floyd)算法。 掌握AOE、AOV网概念,掌握拓扑排序,了解关键路径 数据结构励志照亮人生 编程改变命运26.1 6.1 图图的概念及相关术语的概念及相关术语 零、引假设6个城市间要铺设光纤，城市

2、间的路径长度如图所示。 数据结构励志照亮人生 编程改变命运36.1 6.1 图图的概念及相关术语的概念及相关术语 一、图的概念 1、图的定义：记为G=(V，E)，其中V是顶点的有穷非空集 合，E是边的有穷集合。 VV0, V1, V2, Vn-1，Vi顶点的集合，属于某种数据类型。 E=(V0, V2), (V3, V4), ，其中“（）”可以用“”表示有向边，称为弧。 图是一种m:n（多对多）的关系 。 E=(1,2),(1,3),(2,3),(3,4)E=, 数据结构励志照亮人生 编程改变命运46.1 6.1 图图的概念及相关术语的概念及相关术语 一、图的概念 2、无向图的定义：每条边都是

3、没有方向的图。 3、有向图的定义：每条边都是有方向的图。 数据结构励志照亮人生 编程改变命运56.1 6.1 图图的概念及相关术语的概念及相关术语 二、图的相关术语 1、无向完全图的定义 ：无向图中任意两个顶点之间均有边 相连接 。n个顶点的无向完全图中有n(n-1)/2条边。 2、有向完全图的定义：有向图中任意两个顶点之间均有方 向互为相反两条边相连接 。有向完全图中有n(n-1)条边。 3、无向图中度的定义：与该顶点相关联的边的数目 。 4、有向图中度的定义：出度是以该顶点为始点的边的数目， 入度是以该顶点为终点的边的数目。顶点顶点1的度为的度为2顶点顶点1的出度为的出度为2顶点顶点1的入

4、度为的入度为1 数据结构励志照亮人生 编程改变命运66.1 6.1 图图的概念及相关术语的概念及相关术语 二、图的相关术语 4、子图的定义 ：若图G=(V，E)，G=(V,E)，若V是 V的子集，E是E的子集，则称图G是G的一个子图。 子图子图子图子图 数据结构励志照亮人生 编程改变命运76.1 6.1 图图的概念及相关术语的概念及相关术语 二、图的相关术语 5、路径、简单路径和回路 路径的定义：在无向图中，若顶点Vp到顶点Vq存在一个顶 点序列Vp，V1，V2，Vi，Vq，使得Vp和顶点Vq相通。路径1、3、2、4 简单路径的定义：若Vp到Vq存在一条路径，除了Vp和Vq可 以相同外，其余顶

5、点均不相同，此路径为一条简单路径。简单路径 简单回路或简单环的定义：起点与终点相同的简单路径。简单环 数据结构励志照亮人生 编程改变命运86.1 6.1 图图的概念及相关术语的概念及相关术语 二、图的相关术语 6、连通、连通图、连通分量 连通的定义：若从一个顶点到另一个顶点互有路径。 连通图的定义：无向图中任意两顶点连通。 连通分量的定义：无向图的极大连通子图（连通且子图）。顶点1和4连通顶点2和6非连通此图为非连通图连通分量连通分量注：连通图的连通分量就是本身。注：连通图的连通分量就是本身。 数据结构励志照亮人生 编程改变命运96.1 6.1 图图的概念及相关术语的概念及相关术语 二、图的相

6、关术语 7、强连通图和强连通分量 强连通图的定义：在有向图中任意两个的顶点都连通 。 强连通分量的定义：有向图的极大连通 子图。顶点2和1非连通顶点2和3非连通此图为非强连通图强连通分量强连通分量注：强连通图的强连通分量就是本身。注：强连通图的强连通分量就是本身。 数据结构励志照亮人生 编程改变命运106.1 6.1 图图的概念及相关术语的概念及相关术语 二、图的相关术语 8、边的权、网 边的权（Weight）的定义：与边有关的数据为权。权可以是长度、等级、电流、时间、代价等。 网（Network）的定义：边上带权的图称为网或网络。 数据结构励志照亮人生 编程改变命运116.1 6.1 图图的

7、概念及相关术语的概念及相关术语 二、图的相关术语 9、邻接点 在无向图中，若存在一条边（Vi, Vj），则称Vi和Vj互为邻接点（Adjacent）。 在有向图中，若存在一条弧 ，则称Vi为此弧的起点，称Vj为此弧的终点；称Vi邻接到Vj，Vj邻接自Vi，Vi和Vj互为邻接点。顶点2和3互为邻接点顶点1邻接到顶点2顶点1和3互为邻接点 数据结构励志照亮人生 编程改变命运126.2 6.2 图图的存储结构的存储结构 一、邻接矩阵表示法 1、邻接矩阵是表示顶点之间相邻关系的矩阵(二维数组)。邻接矩阵邻接矩阵邻接矩阵邻接矩阵V0V1V2V30110101111010110对称矩阵 数据结构励志照亮人

8、生 编程改变命运136.26.2图的存储结构图的存储结构 一、邻接矩阵表示法 2、顶点存储：需要一个一维数组来完成。 3、边表的存储：需要一个二维数组（见前）下标0123数组VexsV0V1V2V3 4、顶点数和边数 数据结构励志照亮人生 编程改变命运146.26.2图的存储结构图的存储结构 一、邻接矩阵表示法 5、图的类型定义#define #define MAXVERTEX 100 MAXVERTEX 100 /最大顶点个数#define #define MAXSIZE 100 MAXSIZE 100 /队列最大个数99typedef char typedef char Vertex Ve

9、rtex; ; /设置顶点类型typedef int typedef int Edge Edge; /设置边类型typedef typedef structstruct Vertex Vertex VexsVexsMAXVERTEX; MAXVERTEX; /顶点表 Edge EdgesMAXVERTEXMAXVERTEX; Edge EdgesMAXVERTEXMAXVERTEX; /邻接矩阵，即边表 int int numVexsnumVexs, , numEdgesnumEdges; ; /顶点个数，边个数 MGraphMGraph; ; /定义图 数据结构励志照亮人生 编程改变命运15

10、6.26.2图的存储结构图的存储结构 二、邻接表表示法 1、邻接表表示法类似与树的孩子链表表示法。 2、邻接表的结点结构和数组的结点结构。adjvexnextvertexfirst 边表数组结构 顶点数组结构 邻接表邻接表 数据结构励志照亮人生 编程改变命运166.26.2图的存储结构图的存储结构 二、邻接表表示法 3、定义：边表结点（单链表） 4、定义：顶点表结点（单链表） 5、封装：图的顶点数、边数 数据结构励志照亮人生 编程改变命运176.26.2图的存储结构图的存储结构 一、邻接矩阵表示法 5、图的类型定义#define MAXVERTEX 100 #define MAXVERTEX

11、100 /顶点数最多100typedef char typedef char Vertex; Vertex; /顶点定义为字符/typedef int Edge; /边的权值/(1)定义边表的结点typedef typedef structstruct EdgeNodeEdgeNode int int adjvexadjvex; ; /邻接点域：存储顶点对应的下标 / Edge info; / Edge info; /存储边的权值 structstruct EdgeNodeEdgeNode * *next; next; /指向下一个邻接点 EdgeNodeEdgeNode; ; /边表结点 数

12、据结构励志照亮人生 编程改变命运186.26.2图的存储结构图的存储结构 一、邻接矩阵表示法 5、图的类型定义/(2)定义顶点表的结点typedef typedef structstruct VertexNodeVertexNode Vertex Vertex vexsvexs; ; /顶点域 EdgeNodeEdgeNode * *first; first; /指向该顶点的边表的头指针 VertexNodeVertexNode , , AdjListAdjListMAXVERTEX;MAXVERTEX;/定义邻接表数组，AdjList为顶点表结点的数组类型/(3)定义图typedef typ

13、edef structstruct AdjListAdjList adjListadjList; ; /这是一个数组，见上 int int numVexsnumVexs , , numEdgesnumEdges; ; /图的顶点数、图的边数 GraphAdjListGraphAdjList; ; 数据结构励志照亮人生 编程改变命运196.36.3图的遍历图的遍历 一、深度优先遍历 1、实例描述：选择从淮安出发，然后青岛、烟台、大连、西安、开封、上海、苏州和扬州旅游路线，每一条路线尽量延伸到所有城市。 数据结构励志照亮人生 编程改变命运20首先将出发点V标记为已访问过，然后依次从V出发搜索 V的

14、某个邻接点W，若W未曾访问过，则以W为新的出发 点继续进行深度优先遍历，直至图中所有和源点V有路径 相通的顶点均被访问为止。6.36.3图的遍历图的遍历 一、深度优先遍历 2、深度优先遍历过程V1V2V3V6V5V0V4V7V8回溯假设图G的初始状态是所有顶点均未曾访问过，在G中 任选一顶点为出发点(源点)。遍历结果：遍历结果： V0,V1,V2,V3,V6,V4,V7,V8,V5注：遍历结果不唯一 数据结构励志照亮人生 编程改变命运216.36.3图的遍历图的遍历 二、广度优先遍历 1、实例描述：选择从淮安出发， 然后青岛、开封、扬州、上海、烟台、西安、苏州和大连旅游路线，尽量先旅游附近的城

15、市，然后逐渐扩大范围。 数据结构励志照亮人生 编程改变命运22首先将出发点V标记为已访问过，然后依次从V出发搜索 V的每个邻接点W1，W2，Wn，再依次访问与W1， W2，Wn邻接的所有未曾访问过的顶点，至图中所 有和源点V有路径相通的顶点都已访问到为止。6.36.3图的遍历图的遍历 二、广度优先遍历 2、广度优先遍历过程V1V2V3V6V5V0V4V7V8假设图G的初始状态是所有顶点均未曾访问过，在G中 任选一顶点为出发点(源点)。遍历结果：遍历结果： V0,V1, V3, V4, V5, V2,V6,V7,V8注：遍历结果不唯一注：有点层次遍历的意味 数据结构励志照亮人生 编程改变命运23

16、6.46.4最小生成树最小生成树 一、相关概念 1、生成树的定义：连通图G的一个子图如果是一棵包含G 的所有顶点的树。 2、树的权的定义：生成树各边的权值总和。 3、最小生成树的定义：权最小的生成树，可简记为MST。 举例：图G的顶点表示城市，边表示连接两个城市之间的公路，假设城市之间没有修建任何公路，那么为了把n个城市连接起来，最多可修建n(n-1)/2条公路，最少可修建n-1条公路，则图G的生成树表示了修建公路的可行方案。如果考虑修建造价，那么如何选择n-1条线路，使得修建公路的总造价最小呢？这就是要构造该图的一棵最小生成树。 4、作用 数据结构励志照亮人生 编程改变命运246.46.4最

17、小生成树最小生成树 二、普里姆(Prim)算法 （1）选择一个顶点Vi作为源点， 并纳入集合U=Vi，T=;（2）选择与Vi邻接的顶点中，与Vi构成所有边中权值最小的顶点Vj并纳入集合U=Vi , Vj，T=Eij；（3）选择集合U中的顶点与集合V-U 中顶点邻接的边中，权值最小的顶点Vw，并纳入集合U=Vi , Vj ,Vw中，T=Eij,Eiw或T=Eij,Ejw ；（4）重复第三步，直到U中包含所有顶点，此时U=V，E中必有n-1条边（图G有n个顶点）注：步骤3保证了生成树不会出现回路，因为两个顶点的集合U和V-U，正好其顶点互不相同。假设图为G=(V,E),V为顶点集合，E为边集合。

18、数据结构励志照亮人生 编程改变命运256.46.4最小生成树最小生成树 二、普里姆(Prim)算法 对Prim算法，引入一个辅助数组lowcost 用于保存U集合的顶点到V-U集合中顶点的最小边权值。如果某个顶点已加入U中，设该顶点对应的下标为j，则用lowcostj=0表示。初始时，假设U=V0，所以lowcost 0=0,其余lowcost1n则为V0 到其余顶点的边的权值，如果没有边，则其值可用表示，当然可以用65535等比较大的数字表示，这个比较大的数字可以事先进行预估。 数据结构励志照亮人生 编程改变命运266.46.4最小生成树最小生成树 二、普里姆(Prim)算法 选择从A点出发

19、。U=A，T=（1） U=A,D,T=ADU=A,D,T=AD（2） U=A,D,B,T=AD,ABU=A,D,B,T=AD,AB（3） U=A,D,B,C,T=AD,AB,DC U=A,D,B,C,T=AD,AB,DCABCDEFG2271106458413ABCD221顶点ABCDEFG值0241顶点ABCDEFG值0220784顶点ABCDEFG值0020784 数据结构励志照亮人生 编程改变命运276.46.4最小生成树最小生成树 二、普里姆(Prim)算法 ABCDEFG2271106458413（4） U=A,D,B,C,G,T=AD,AB,DC,DGU=A,D,B,C,G,T=A

20、D,AB,DC,DG（5）U=A,D,B,C,G,F,T=AD,AB,DC,DG,GFU=A,D,B,C,G,F,T=AD,AB,DC,DG,GF（6） U=A,D,B,C,G,F,E,T=AD,AB,DC,DG,GF,GE U=A,D,B,C,G,F,E,T=AD,AB,DC,DG,GF,GE此时，所有结点都变为0,全部加入U中。ABCDEFG221641顶点ABCDEFG值0000754顶点ABCDEFG值0000610顶点ABCDEFG值0000600 数据结构励志照亮人生 编程改变命运286.46.4最小生成树最小生成树 三、克鲁斯卡尔(Kruskal)算法 选择一条权值最小的边，并纳

21、入集合E1 ；在剩下的边当中再选择一条权值最小的边，并纳入集合E1，E2；重复执行第二步，直到边集合中已经包含图G所有顶点为止（不允许出现回路）。 数据结构励志照亮人生 编程改变命运296.46.4最小生成树最小生成树 三、克鲁斯卡尔(Kruskal)算法 ABCDEFG2271106458413（1）T=AD（2）T=AD,FGAD1FG1（3）T=AD,FG,ABB2（4）T=AD,FG,AB,CDC2（5）T=AD,FG,AB,CD,DG4（6）T=AD,FG,AB,CD,DG,GEE 数据结构励志照亮人生 编程改变命运30106.56.5最短路径最短路径 一、单源最短路径 1、单源最短

22、路径的定义:在有向网中，从某个源点V0出发 到其它各个顶点的最短路径。12354209050302040 2、单源最短路径求解方法： 迪杰斯特拉(Dijkstra) 方法循循 环环S SW Wd2 d3 d4 d5d2 d3 d4 d5p2 p3 p4 p5p2 p3 p4 p5初始化1-20 30 90 1 1 1 111,2220 70 30 901 2 1 121,2,4420 40 30 701 4 1 431,2,4,3320 40 30 601 4 1 341,2,4,3,5520 40 30 601 4 1 3 数据结构励志照亮人生 编程改变命运316.56.5最短路径最短路径

23、一、单源最短路径 1、单源最短路径的定义:在有向网中，从某个源点V0出发 到其它各个顶点的最短路径。 2、单源最短路径求解方法： 迪杰斯特拉(Dijkstra) 方法 数据结构励志照亮人生 编程改变命运32ABCDEFG2221106458413一、单源最短路径 6.56.5最短路径最短路径 迪杰斯特拉(Dijkstra) 方法步骤，假设从A点出发。顶点ABCDEFG距离021已知1000000路径AAAB-1AD-1-1-1（1）从A结点出发，计算出A到其他顶点的距离，标记A到自己的距离为已知最短距离。（与A未邻接的顶点标识为） 数据结构励志照亮人生 编程改变命运33ABCDEFG22211

24、06458413一、单源最短路径 6.56.5最短路径最短路径 迪杰斯特拉(Dijkstra) 方法步骤，假设从A点出发。顶点ABCDEFG距离0231395已知1001000路径AAABADCADADEADFADG（2）从上表可知，A到D的距离为1，是所有未知顶点中距离最短的一个，标记到D的距离为已知，并重新计算A到【与D相邻】的未知顶点的距离。 数据结构励志照亮人生 编程改变命运34ABCDEFG2221106458413一、单源最短路径 6.56.5最短路径最短路径 迪杰斯特拉(Dijkstra) 方法步骤，假设从A点出发。顶点ABCDEFG距离0231395已知1101000路径AAA

25、BADCADADEADFADG（3）从上表可知，A到B的距离为2，是所有未知顶点中距离最短的一个，标记到B的距离为已知，并重新计算到其他顶点的距离（只涉及与B邻接的未知顶点）。此时因为从A经过B到E的距离2+10=123（原从A经过D到E的距离为3），故不做调整。 数据结构励志照亮人生 编程改变命运35ABCDEFG2221106458413一、单源最短路径 6.56.5最短路径最短路径 迪杰斯特拉(Dijkstra) 方法步骤，假设从A点出发。顶点ABCDEFG距离0231385已知1111000路径AAABADCADADEADCFADG（4）从上表可知，A到C的距离为2，是所有未知顶点中距

26、离最短的一个，标记到C的距离为已知，并重新计算到其他顶点的距离（只涉及与C邻接的未知顶点）。此时因为从A经过D、C到F的距离3+5=85（原从A经过D到G的距离为5），故不做调整。 数据结构励志照亮人生 编程改变命运37ABCDEFG2221106458413一、单源最短路径 6.56.5最短路径最短路径 迪杰斯特拉(Dijkstra) 方法步骤，假设从A点出发。顶点ABCDEFG距离0231365已知1111101路径AAABADCADADEADGFADG（6）从上表可知，A到G的距离为5，是所有未知顶点中距离最短的一个，标记到G的距离为已知，并重新计算到其他顶点的距离（只涉及与G邻接的未知

27、顶点）。此时因为从A经过D、G到F的距离5+1=68（原从A经过D、C到F的距离为8），故应做调整。 数据结构励志照亮人生 编程改变命运38ABCDEFG2221106458413一、单源最短路径 6.56.5最短路径最短路径 迪杰斯特拉(Dijkstra) 方法步骤，假设从A点出发。顶点ABCDEFG距离0231365已知1111111路径AAABADCADADEADGFADG（7）从上表可知，最后还有一个结点未知，标记这个结点为已知，整个算法结束，从A结点到其他顶点的最短距离算出，且路径也找出来了。 数据结构励志照亮人生 编程改变命运39ABCDEFG2221106458413一、单源最短

28、路径 6.56.5最短路径最短路径 迪杰斯特拉(Dijkstra) 方法步骤:（1）设置两个数组，数组d 表示从源点到其他顶点的距离，数组f j的为1表示从源点到下标为j的顶点的最短距离和路径已经计算出，为0表示还不确定是否为最短距离和路径。当然应该设置一个数组保存路径。（此次略） 数据结构励志照亮人生 编程改变命运40ABCDEFG2221106458413一、单源最短路径 6.56.5最短路径最短路径 迪杰斯特拉(Dijkstra) 方法步骤:（2）在未确定最短距离和路径的顶点中找到最小距离的顶点，标识其为已确定最短距离和路径（即已知，设置f 数组）。重新计算源点到未确定最短距离和路径的顶

29、点的最短距离和路径，这时只需要重新计算与刚才标识已确定最短距离和路径的顶点邻接的顶点的最短距离和路径。（3）重复上面的步骤，直到f 数组所有的值都为1。 数据结构励志照亮人生 编程改变命运416.56.5最短路径最短路径 二、每一对顶点之间的最短路径 1、求解方法：（1）每个顶点做为源点，调用Dijkstra算法n次，可求解到每对顶点之间的最短距离。算法时间复杂度O(n3)。（2）使用Floyd算法，其算法时间复杂度也是O(n3)。Floyd算法更简洁、更优美，实际为一个三重循环。for(k=0;for(k=0;kkG.numVexsG.numVexs;+k);+k) for(v=0 for(

30、v=0; ;vvG.numVexsG.numVexs;+v);+v) for(w=0for(w=0; ;wwdisvdisvkk+disk+diskw)w) disv disvww=disv=disvkk+disk+diskww; ; pathv pathvww=pathv=pathvkk; ; 数据结构励志照亮人生 编程改变命运426.56.5最短路径最短路径 二、每一对顶点之间的最短路径 2、Floyd算法思想动态规划算法（1）动态规划算法通常用于求解具有某种最优性质最优性质的问题。（2）最优性质的问题可能有很多解法，需要找到最优的解法。（3）基本思想：将待解问题分解成若干子问题，先求解子

31、问题的最优解，通过子问题的最优解最终求得问题的最优解。注意：这些子问题往往不是独立的，因此需要保存这些子问题的最优解。（4）动态规划算法（子问题不独立，每步可改变）、分治算法（子问题相互独立）、贪心算法（每步不可改变） 数据结构励志照亮人生 编程改变命运436.56.5最短路径最短路径 二、每一对顶点之间的最短路径 2、Floyd算法思想（1）问题描述：计算任意顶点i到任意顶点j的最短距离。（2）问题分解：两种可能，一是顶点i直接到顶点j的距离为最短，二是顶点i经过若干顶点后到j的距离最短。如下图包含三个结点的简单图。很明显AB的最短路径为：ACB，最短距离为3。ABC125（3）对每一结点k

32、，检查disik+diskjdisij是否成立，如果成立则表示经过结点k的距离比i直接到j的距离短，记录下这个前趋结点k到数组pathij中，表示i到j需经过结点k。 数据结构励志照亮人生 编程改变命运446.56.5最短路径最短路径 二、每一对顶点之间的最短路径 3、Floyd算法的手工计算十字交叉法（1）方法：对任意k（0=kn）,在邻接矩阵中a、画线：画出第k行、第k列和由00位置开始的对角线。b、不在上面的三条线中的元素假设为ij，与对应的第第k行、第k列的元素ik、kj、kk组成一个二阶矩阵。c、不在上面的三条线中的元素假设为ij，与对应的第第k行、第k列的元素ik、kj、kk组成一

33、个二阶矩阵。d、在组成的这些二阶矩阵中，计算两对角线元素之和。如果不在三条线的元素所在的对角线大于另一条对角线，则该元素应被这条对角线之和替代。路径数组pathij=k。 数据结构励志照亮人生 编程改变命运456.56.5最短路径最短路径 二、每一对顶点之间的最短路径 4、Floyd算法的手工计算实例61405k=2dis45=6,这是直接距离diskk始终应为0，dis42+ dis25,这个正好是经过k=2这个顶点的距离。path45=k0 1 2 3 4 5 6 0123456 数据结构励志照亮人生 编程改变命运466.56.5最短路径最短路径 二、每一对顶点之间的最短路径 4、Floy

34、d算法的手工计算初始状态ABDC013251732342A0B1C2D3A 0057B 1042C 23302D 310邻接矩阵表(dis数组)A0B1C2D3A 0-1-1-1-1B 1-1-1-1-1C 2-1-1-1-1D 3-1-1-1-1前趋矩阵表(path数组) 数据结构励志照亮人生 编程改变命运476.56.5最短路径最短路径 二、每一对顶点之间的最短路径 4、Floyd算法的手工计算1）k=0ABDC013251732342A0B1C2D3A 0057B 1042C 23302D 310邻接矩阵表(dis数组)040720533073205 01（1） （2）（3）（4）（5）

35、 （6）上面所有二阶矩阵黄色对角线之和皆小于白色对角线之和，故不调整。 数据结构励志照亮人生 编程改变命运486.56.5最短路径最短路径 二、每一对顶点之间的最短路径 4、Floyd算法的手工计算2）k=1ABDC013251732342A0B1C2D3A 0057B 1042C 23302D 310邻接矩阵表(dis数组)504570203302320 041（1） （2）（3）（4）（5） （6）上面所有二阶矩阵中(1)中的需要调整为9 数据结构励志照亮人生 编程改变命运496.56.5最短路径最短路径 二、每一对顶点之间的最短路径 4、Floyd算法的手工计算2）k=1ABDC0132

36、51732342A0B1C2D3A 0057B 1042C 23302D 310邻接矩阵表(dis数组)A0B1C2D3A 0-1-1-1-1B 1-1-1-1-1C 2-1-1-1-1D 3-1-1-1-1前趋矩阵表(path数组)91 数据结构励志照亮人生 编程改变命运506.56.5最短路径最短路径 二、每一对顶点之间的最短路径 4、Floyd算法的手工计算3）k=2ABDC013251732342A0B1C2D3A 00597B 1042C 23302D 310邻接矩阵表(dis数组)593097024304202301301（1） （2）（3）（4）（5） （6）上面所有二阶矩阵中(

37、3)、(5)、(6)中的分别需要调整为7、4、4 数据结构励志照亮人生 编程改变命运516.56.5最短路径最短路径 二、每一对顶点之间的最短路径 4、Floyd算法的手工计算3）k=2ABDC013251732342A0B1C2D3A 00597B 1042C 23302D 310邻接矩阵表(dis数组)A0B1C2D3A 0-1-11-1B 1-1-1-1-1C 2-1-1-1-1D 3-1-1-1-1前趋矩阵表(path数组)744222 数据结构励志照亮人生 编程改变命运526.56.5最短路径最短路径 二、每一对顶点之间的最短路径 4、Floyd算法的手工计算4）k=3ABDC013

38、251732342A0B1C2D3A 00597B 17042C 23302D 34410邻接矩阵表(dis数组)574097127240421032403240（1） （2）（3）（4）（5） （6）上面所有二阶矩阵中(2)、(3)、(4)中的9、7、4分别需要调整为8、6、3 数据结构励志照亮人生 编程改变命运536.56.5最短路径最短路径 二、每一对顶点之间的最短路径 4、Floyd算法的手工计算4）k=3 结束！ABDC013251732342A0B1C2D3A 00597B 17042C 23302D 34410邻接矩阵表(dis数组)A0B1C2D3A 0-1-11-1B 12-

39、1-1-1C 2-1-1-1-1D 322-1-1前趋矩阵表(path数组)863333 数据结构励志照亮人生 编程改变命运546.56.5最短路径最短路径 二、每一对顶点之间的最短路径 4、Floyd算法的手工计算5）路径推导ABDC013251732342A0B1C2D3A 0-1-13-1B 13-13-1C 2-1-1-1-1D 322-1-1前趋矩阵表(path数组)从前趋矩阵表(path数组)推导路径：例:BA,其前趋为3,即D而DA,其前趋为2,即CCA，其前趋为-1,表示其直接距离为最短路径。故BA的路径为:BDCA，最短路径长度为6。 数据结构励志照亮人生 编程改变命运556

40、.66.6拓扑排序与关键路径拓扑排序与关键路径一、基本概念1、DAG图无环的有向图称为有向无环图，Directed Acycline Graph。DAG图是描述工程或系统进程的有效工具。如大学课程，有些课程必须先学，只有修学了某些课程后，才能修读另外的课程；同样，工程上，某些任务必须在完成其他任务的情况下才能开始，这些都可用DAG图来描述。AOV网：在图中，用顶点表示活动，用边表示优先关系的有向图称为AOV网（Activity on Vertex Network）。AOE网：在图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动持续的时间，这种用边表示活动的有向图称为AOE网（Acti

41、vity on Edge Network）。 数据结构励志照亮人生 编程改变命运566.66.6拓扑排序与关键路径拓扑排序与关键路径一、基本概念课程编号课程名称先修课程C1信息基础无C2数据结构C1、C4C3网页制作C1C4C语言程序设计C1C5AC2、C3、C4C6JavascriptC3C7数据库C2、C9C8JavaC4C9软件工程C2C1C1C3C3C4C4C2C2C6C6C8C8C9C9C7C7C5C5AOV网：顶点表示活动，边表示活动间优先关系 数据结构励志照亮人生 编程改变命运576.66.6拓扑排序与关键路径拓扑排序与关键路径一、基本概念V0V0V2V2V1V1V3V3V4V4

42、V5V5V6V6V7V7V8V8V9V9a0=3a1=4a3=6a7=9a5=7a9=6a11=5a12=3a10=2a8=4a4=8a2=5a6=3AOE网：顶点表示事件，边表示活动，边上权表示持续时间 数据结构励志照亮人生 编程改变命运586.6 6.6 拓扑排序与关键路径拓扑排序与关键路径一、基本概念2、拓扑排序（AOV网）拓扑序列：有向图G=(V,E),有n个顶点，V中序列满足条件: (1)顶点vi到顶点vj有一条路径，且vi必须排在vj之前;(2)顶点vi到顶点vj没有路径,则为其安排一个先后顺序。如果有向图G所有的顶点都在拓扑序列中，则则AOVAOV网不存网不存在环。在环。拓扑排序

43、：实现有向图的拓扑序列的过程称为拓扑排序。如前面AOV图的拓扑排序为:C1 C3 C4 C2 C6 C5 C8 C9 C7（拓扑排序不唯一） 数据结构励志照亮人生 编程改变命运596.6 6.6 拓扑排序与关键路径拓扑排序与关键路径一、基本概念3、关键路径（AOE网）源点：在一般工程中，都有一个开始点（入度为0），称为源点；都有一个完成点（出度为0）称为汇点。在AOE网中，把路径上各个活动持续的时间之和称为路径长度。从源点到汇点具有最大长度的路径称为关键路径关键路径，在关键路径上的活动称为关键活动。前面AOE网中的关键路径为:V0V2V3V4V7V8 V9。 数据结构励志照亮人生 编程改变命运606.66.6拓扑排序与关键路径拓扑排序与关键路径二、拓扑排序算法1、步骤（1）在有向图中选一个入度为0的顶点，并输出该顶点。（2）从图中删除该顶点和所有以它为始点的边（弧）。（3）重复执行步骤（1）、（2），直到找