数据结构 第七章图精.ppt

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

1、数据结构 第七章图第1页，本讲稿共99页2【重点掌握重点掌握】：1.1.图的两种遍历方法：遍历的定义、深度优先搜索遍历和广度优先搜图的两种遍历方法：遍历的定义、深度优先搜索遍历和广度优先搜索遍历的算法；索遍历的算法；2.2.应用图的遍历算法判断图的连通性及求图的生成树；应用图的遍历算法判断图的连通性及求图的生成树；3.3.用用PrimPrim、KruskalKruskal算法求图的最小生成树；算法求图的最小生成树；4.4.用用DijkstraDijkstra算算法法求求解解单单源源最最短短路路径径问问题题；用用FloydFloyd算算法法求求所所有有顶顶点间的最短路径问题；点间的最短路径问题；

2、5.5.利用利用AOVAOV网进行拓扑排序；利用网进行拓扑排序；利用AOEAOE网求关键路径问题；网求关键路径问题；【掌掌 握握】：1.1.掌握图的定义和术语；掌握图的定义和术语；2.2.图的各种存储结构及其构造算法、在实际问题中的求解效率。图的各种存储结构及其构造算法、在实际问题中的求解效率。第2页，本讲稿共99页37.3 7.3 图的遍历图的遍历 7.3 7.3 图的遍历：图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。顶点仅访问一次。图结构的遍历复杂性：图结构的遍历复杂性：（1 1）在图结构中，没有一个）在图结构中，没有一

3、个“自然自然”的首结点，图中的任意一个顶的首结点，图中的任意一个顶点都可以作为第一个被访问的结点点都可以作为第一个被访问的结点（2 2）在非连通图中，从一个顶点出发，只能访问它所在的连通分量上）在非连通图中，从一个顶点出发，只能访问它所在的连通分量上的所有顶点，因此，还需考虑的所有顶点，因此，还需考虑如何选取下一个出发点如何选取下一个出发点以访问图中的以访问图中的其余连通分量其余连通分量（3 3）在图结构中，如果有回路存在，那么一个顶点被访问后，有可）在图结构中，如果有回路存在，那么一个顶点被访问后，有可能沿回路又回到该顶点，考虑能沿回路又回到该顶点，考虑如何避免重复访问如何避免重复访问（4

4、4）在图结构中，一个顶点可以和其他多个顶点邻接，当这样的顶点）在图结构中，一个顶点可以和其他多个顶点邻接，当这样的顶点访问过后，考虑访问过后，考虑如何选取下一个要访问的顶点的问题如何选取下一个要访问的顶点的问题第3页，本讲稿共99页4 图的遍历方法有深度优先遍历和广度优先遍历两种。图的遍历方法有深度优先遍历和广度优先遍历两种。7.3.1 深度优先搜索深度优先搜索方法：方法：（1 1）从图的某一顶点）从图的某一顶点V V0 0出发，访问此顶点；出发，访问此顶点；（2 2）依次从）依次从V V0 0的未被访问的邻接点出发，深度优先遍历图，直至的未被访问的邻接点出发，深度优先遍历图，直至图中所有和图

5、中所有和V V0 0相通的顶点都被访问到。相通的顶点都被访问到。若此时图中尚有顶点若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问到。过程，直至图中所有顶点都被访问到。第4页，本讲稿共99页5 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1若图的存储结构为邻接表，则若图的存储结构为邻接表，则访问邻接点的顺序不唯一，访问邻接点的顺序不唯一，深度优先序列不是唯一的深度优先序列不是唯一的 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4

6、V4 V0,V1,V3,V4,V7,V2,V5,V6,V0,V1,V3,V4,V7,V2,V5,V6,求图求图G以以V0为起点的的深度优先序列（设存储结构为邻接矩阵）为起点的的深度优先序列（设存储结构为邻接矩阵）第5页，本讲稿共99页6void DFS(Graph G,int v)/*从第从第v个顶点出发，递归地深度优先遍历图个顶点出发，递归地深度优先遍历图G*/*v是顶点在一维数组中的位置，假设是顶点在一维数组中的位置，假设G是非空图是非空图*/visitedv=1;Visit(v);/*访问第访问第v个顶点个顶点*/for(w=FirstAdjVex(G,v);w;w=NextAdjVex

7、(G,v,w)if(!visitedw)DFS(G,w);/*对对v的尚未访问的邻接顶点的尚未访问的邻接顶点w递归调用递归调用DFS*/辅助数组：辅助数组：int visitedMax_Vertex_Num;访问标志数组访问标志数组,全局变量，初始时所有分量全为全局变量，初始时所有分量全为0，visitedv=1表示顶点表示顶点v v已被访问已被访问.visited0123400000深度优先遍历算法深度优先遍历算法:7.3 7.3 图的遍历图的遍历第6页，本讲稿共99页77.3 7.3 图的遍历图的遍历在在在在邻接表邻接表邻接表邻接表存储结构上实现深度优先搜索存储结构上实现深度优先搜索存储结

8、构上实现深度优先搜索存储结构上实现深度优先搜索:void DFSTraverseAL(ALGraph G)/*深度优先遍历以邻接表存储的图深度优先遍历以邻接表存储的图G*/int i;for(i=0;iG.vexnum;+i)visitedi=0;/*标志数组初始化标志数组初始化*/for(i=0;inextarc)w=p-adjvex;/*w是是v的邻接顶点的序号的邻接顶点的序号*/if(!visitedw)DFSAL(G,w);/*若若w尚未访问尚未访问,递归调用递归调用DFS*/*DFSAL*/7.3 7.3 图的遍历图的遍历第8页，本讲稿共99页9 在遍历时，对图中每个顶点至多调用一次

9、在遍历时，对图中每个顶点至多调用一次DFSDFS函数，因为一旦某函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。费的时间则取决于所采用的存储结构。用邻接矩阵做图的存储结构时，查找用邻接矩阵做图的存储结构时，查找各个各个顶点的邻接点所需的时间顶点的邻接点所需的时间为为O(n2)，其中，其中n n为图中顶点数。当以邻接矩阵做存储结构时，深度为图中顶点数。当以邻接矩阵做存储结构时，深度

10、优先搜索遍历图的时间复杂度为优先搜索遍历图的时间复杂度为O(n2+n)。当以邻接表做图的存储结构时，找邻接点所需时间为当以邻接表做图的存储结构时，找邻接点所需时间为O(e)，其其中中e e为无向图中边的数或有向图中弧的数。因此，当以邻接表为无向图中边的数或有向图中弧的数。因此，当以邻接表做存储结构时，深度优先搜索遍历图的时间复杂度为做存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。7.3 7.3 图的遍历图的遍历第9页，本讲稿共99页10图中某顶点图中某顶点v v出发：出发：1 1）访问顶点）访问顶点v v；2 2）访问）访问v v的所有未被访问的邻接点的所有未被访问的邻接点w w1

11、 1,w,w2 2,w,wk k ；3 3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点）依次从这些邻接点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；依此类推，直到图中所有访问过的顶点的邻接点都被访问；7.3.2 广度优先遍历广度优先遍历7.3 7.3 图的遍历图的遍历第10页，本讲稿共99页11 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0,V1,V2,V3,V4,V7,V5,V6 V0,V1,V2,V3,V4,V7,V5,V6 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5

12、V4V4若图的存储结构为邻接表，则若图的存储结构为邻接表，则访问邻接点的顺序不唯一，访问邻接点的顺序不唯一，深度优先序列不是唯一的深度优先序列不是唯一的求图求图G以以V0为起点的的广度优先序列（设存储结构为邻接矩阵）为起点的的广度优先序列（设存储结构为邻接矩阵）先被访问的顶点，其邻先被访问的顶点，其邻接点也要先被访问接点也要先被访问设一队列保存已访问的设一队列保存已访问的顶点顶点第11页，本讲稿共99页12Q 在邻接表存储结构上的广度优先搜索在邻接表存储结构上的广度优先搜索V0V0V1V1V2V2V3V3V4V4V7V7V5V5V6V6V1V1V2V2V3V3V0V0V4V4V7V7V5V5V

13、6V6 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V17.3 7.3 图的遍历图的遍历7012V0V2V3V1datafirstarc 0 1adjvex next3V4 3 0 5 1 1 2 7456 4V5V6V7 2 6 2 5 1 4 7 6第12页，本讲稿共99页13void BFSTraverse(MGraph G)/*从从v出发，广度优先遍历连通图出发，广度优先遍历连通图G*/*使用辅助队列使用辅助队列Q和访问标志数组和访问标志数组visited*/for(v=0;vG.vexnum;+i)visitedv=0;InitQueue

14、(Q,G.vexnum);/*初始化空的辅助队列初始化空的辅助队列Q*/for(v=0;vG.vexnum;+v)if(!visitedv)/*若若v尚未访问尚未访问*/visitedv=1;Visit(v);EnQueue(Q,v);while(!QueueEmpty_Sq(Q)DeQueue(Q,u);/*队头元素出队队头元素出队,并赋值给并赋值给u*/*访问访问u所有未被访问的邻接点所有未被访问的邻接点*/for(w=0;wG.vexnum;w+;)if(G.arcsu,w.adj&!visitedw)visitedw=1;Visit(w);EnQueue(Q,w);/*while*/*

15、BFSTraverse*/7.3 7.3 图的遍历图的遍历第13页，本讲稿共99页14第七 章 图 7.4 连通网的最小生成树连通网的最小生成树 7.4.1 生成树生成树 7.4.2 最小生成树最小生成树 7.4.3 构造最小生成树的构造最小生成树的Prim算法算法 7.4.4 构造最小生成树的构造最小生成树的Kruskal算法算法第14页，本讲稿共99页157.4.1 生成树生成树生成树：生成树：包含了无向图包含了无向图G G所有顶点的所有顶点的极小极小连通子图。连通子图。1 1）“极小极小”含义：一个有含义：一个有n n个顶点的连通图的生成树有个顶点的连通图的生成树有n-1n-1条边，条边

16、，删除任何一条边，子图不再连通；在生成树中再加一条边必删除任何一条边，子图不再连通；在生成树中再加一条边必然形成回路。（生成树包含了图中的所有顶点，但只有足以然形成回路。（生成树包含了图中的所有顶点，但只有足以构成生成树的构成生成树的n-1n-1条边）条边）2 2）一个图可以有许多棵不同的生成树；）一个图可以有许多棵不同的生成树；3 3）生成树中任意两个顶点间的路径是唯一的；）生成树中任意两个顶点间的路径是唯一的；4 4）含）含n n个顶点个顶点n-1n-1条边的图不一定是生成树。条边的图不一定是生成树。7.4 7.4 最小的生成树最小的生成树第15页，本讲稿共99页167.4 7.4 最小的

17、生成树最小的生成树 生成树的含义：生成树的含义：生成树的含义：生成树的含义：n n个顶点的图最多可存在个顶点的图最多可存在n(n-1)/2n(n-1)/2条边线路。条边线路。求生成树是为了在网络中连通求生成树是为了在网络中连通n n个顶点而选择最少的边个顶点而选择最少的边(n(n1)1)。例如：一个通信网络中，节点代表了路由器，为了使各路由例如：一个通信网络中，节点代表了路由器，为了使各路由器之间是连通的（数据可达），且不形成回路器之间是连通的（数据可达），且不形成回路(数据回到发送方数据回到发送方)，则需建立该网络的生成树。，则需建立该网络的生成树。第16页，本讲稿共99页17求生成树的方法

18、：求生成树的方法：求生成树的方法：求生成树的方法：利用遍历算法。利用遍历算法。从连通图中的任一顶点出发进行遍历时，除出发点外，从连通图中的任一顶点出发进行遍历时，除出发点外，其余顶点必须通过一条边才能到达，所以遍历过程中经其余顶点必须通过一条边才能到达，所以遍历过程中经历的边有历的边有n-1n-1条，它和条，它和n n个顶点组成了连通图的一棵生成树。个顶点组成了连通图的一棵生成树。由深度优先搜索得到的是深度优先生成树；由广度优先由深度优先搜索得到的是深度优先生成树；由广度优先搜索得到的是广度优先生成树。搜索得到的是广度优先生成树。第17页，本讲稿共99页18 V0 V0 V7 V7 V6 V6

19、 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1深度遍历：深度遍历：V0V1V3V4V7V2 V5V6 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V17.4 7.4 最小的生成树最小的生成树 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1深度优先搜索生成树深度优先搜索生成树第18页，本讲稿共99页19广度遍历：广度遍历：V0 V1 V2 V3 V4 V7 V5 V6 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1 V0 V0 V7 V7 V

20、6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1广度优先搜索生成树广度优先搜索生成树7.4 7.4 最小的生成树最小的生成树 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1第19页，本讲稿共99页207.4.2 最小生成树的概念最小生成树的概念 由生成树的定义可知，无向连通图的生成树不是惟一的。由生成树的定义可知，无向连通图的生成树不是惟一的。问题的提出：问题的提出：设要在设要在n n个城市间建立通信联络网，顶点个城市间建立通信联络网，顶点表示城表示城市，权表示城市间建立通信线路所需花费代价。希望找到一棵生成树，市，权表示城市

21、间建立通信线路所需花费代价。希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小最小代价生成树。最小代价生成树。7.4 7.4 最小的生成树最小的生成树第20页，本讲稿共99页21 最小生成树定义：最小生成树定义：对于一个网络，它的所有生成树中边权值对于一个网络，它的所有生成树中边权值最小的生成树称为最小生成树。最小的生成树称为最小生成树。问题分析：问题分析：n n个城市间建立通信网，如何在可能的线路中选择个城市间建立通信网，如何在可能的线路中选择n-1n-1条，能把所有城市（顶点）均连起来，且总耗费（各边

22、条，能把所有城市（顶点）均连起来，且总耗费（各边权值之和）最小。权值之和）最小。即：如何在保证即：如何在保证n点连通的前题下最节省点连通的前题下最节省经费经费?第21页，本讲稿共99页221.1.Prim 法基本步骤法基本步骤 设连通网络设连通网络设连通网络设连通网络G=V,E。集合。集合。集合。集合U存放存放存放存放G的最小生成树中的顶点，的最小生成树中的顶点，的最小生成树中的顶点，的最小生成树中的顶点，集合集合集合集合T存放最小生成树之外的顶点。存放最小生成树之外的顶点。存放最小生成树之外的顶点。存放最小生成树之外的顶点。(1)从从从从G中选择某一顶点中选择某一顶点中选择某一顶点中选择某一

23、顶点u u u u0 0 0 0出发，在与它关联的边中选择一个边权出发，在与它关联的边中选择一个边权出发，在与它关联的边中选择一个边权出发，在与它关联的边中选择一个边权最小的边最小的边最小的边最小的边(u(u(u(u0 0 0 0,v);,v);,v);,v);将顶点将顶点将顶点将顶点v v v v加入最小生成树的加入最小生成树的加入最小生成树的加入最小生成树的顶点集合顶点集合顶点集合顶点集合U U U U，在，在，在，在集集集集合合合合T T T T 中删除该顶点；中删除该顶点；中删除该顶点；中删除该顶点；(2)用顶点用顶点用顶点用顶点v v v v到集合到集合到集合到集合T T T T中顶

24、点的边权中顶点的边权中顶点的边权中顶点的边权“更新更新更新更新”原集合原集合原集合原集合U U U U中顶点到中顶点到中顶点到中顶点到集合集合集合集合T T T T中顶点的最小边权；中顶点的最小边权；中顶点的最小边权；中顶点的最小边权；(3)从一个顶点在从一个顶点在从一个顶点在从一个顶点在U中，而另一个顶点在中，而另一个顶点在中，而另一个顶点在中，而另一个顶点在T T T T中的各条边中选择权值最中的各条边中选择权值最中的各条边中选择权值最中的各条边中选择权值最小的边小的边小的边小的边(u,v),把顶点把顶点把顶点把顶点v v v v加入到加入到加入到加入到集合集合集合集合U U U U 中。

25、中。中。中。(4)重复重复重复重复(2)、(3)，直到网络中的所有顶点都加入到生成树顶点集合，直到网络中的所有顶点都加入到生成树顶点集合，直到网络中的所有顶点都加入到生成树顶点集合，直到网络中的所有顶点都加入到生成树顶点集合U中为止。中为止。中为止。中为止。7.4.3 构造最小生成树的构造最小生成树的PrimPrim算法算法7.4 7.4 最小的生成树最小的生成树第22页，本讲稿共99页23V3V3V1V1V4V4V6V6V5V5V2V2651U=V1 V3V3V1V1V4V4V6V6V5V5V2V251654V3V3V4V4V6V6V5V5V2V21V1V1U=V1,V3 U=V1,V3 V

26、3V3V1V1V4V4V6V6V5V5V2V216542V3V3V1V1V4V4V6V6V5V5V2V251654U=V1,V3,V6U=V1,V3,V67.4 7.4 最小的生成树最小的生成树V3V3V1V1V4V4V6V6V5V5V2V236521655462.2.过程演示过程演示第23页，本讲稿共99页24V3V3V1V1V4V4V6V6V5V5V2V216542U=V1,V3,V6,V4U=V1,V3,V6,V4 V3V3V1V1V4V4V6V6V5V5V2V216542U=V1,V3,V6,V4,V2 U=V1,V3,V6,V4,V2 V3V3V1V1V4V4V6V6V5V5V2V2

27、15423U=V1,V3,V6,V4,V2,V5 U=V1,V3,V6,V4,V2,V5 7.4 7.4 最小的生成树最小的生成树V3V3V1V1V4V4V6V6V5V5V2V23652165546Prim 算法的时间复杂度为算法的时间复杂度为O(n2)第24页，本讲稿共99页257.4.3 7.4.3 构造最小生成树的构造最小生成树的KruskalKruskal算法算法1.1.基本思想：按网中权值递增的顺序构造最小生成树。基本思想：按网中权值递增的顺序构造最小生成树。2.2.基本步骤基本步骤 1 1）设连通网）设连通网G=(V,E)G=(V,E)，令最小生成树初始状态是只有，令最小生成树初始

28、状态是只有n n个顶点而个顶点而无边的非连通图无边的非连通图T=(V,T=(V,)，每个顶点自成一个连通分量；，每个顶点自成一个连通分量；2 2）在）在E E中选取代价最小的边，若该边依附的顶点落在中选取代价最小的边，若该边依附的顶点落在T T中不同中不同的连通分量上，则将此边加入到的连通分量上，则将此边加入到T T中；否则，舍去此边，选取中；否则，舍去此边，选取下一条代价最小的边；下一条代价最小的边；3 3）依此类推，直至）依此类推，直至T T中所有顶点都在同一连通分量上为止。中所有顶点都在同一连通分量上为止。7.4 7.4 最小的生成树最小的生成树第25页，本讲稿共99页26V3V3V1V

29、1V4V4V6V6V5V5V2V2V3V3V4V4V6V6V5V5V2V21V1V1V3V3V1V1V4V4V6V6V5V5V2V212V3V3V1V1V4V4V6V6V5V5V2V2123V3V3V1V1V4V4V6V6V5V5V2V2164237.4 7.4 最小的生成树最小的生成树V3V3V1V1V4V4V6V6V5V5V2V236521655463.3.过程演示过程演示第26页，本讲稿共99页27V3V3V1V1V4V4V6V6V5V5V2V2165423V3V3V1V1V4V4V6V6V5V5V2V236521655467.4 7.4 最小的生成树最小的生成树Kruskal 算法的时

30、间复杂度为算法的时间复杂度为O(ne)。第27页，本讲稿共99页28 7.5 7.5 单源最短路径单源最短路径(Shortest Path)(Shortest Path)从一个源点到其他各点的最短路径从一个源点到其他各点的最短路径第28页，本讲稿共99页29 交交通通咨咨询询系系统统、通通讯讯网网、计计算算机机网网络络中中经经常常要要寻寻找找两两结结点点间间最最短短路路径径。例例如如：交交通通咨咨询询系系统统中中：咨咨询询A A到到B B的的最最短短路路径径；计计算算机机网网中中如如何何发发送送E-mailE-mail才才最最节节省省费费用用（使使E-mailE-mail由由A A到到B B沿

31、沿最最短短路路径径传传送送）。）。设用带权的有向图表示一个交通运输网，图中：设用带权的有向图表示一个交通运输网，图中：顶点顶点表示城市表示城市 边边表示城市间的交通联系表示城市间的交通联系 权权表示此线路的长度或沿此线路运输所花的时间或费用等表示此线路的长度或沿此线路运输所花的时间或费用等 这类问题归结为从某顶点出发，沿图的边到达另一顶点所经这类问题归结为从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径过的路径中，各边上权值之和最小的一条路径最短路径。最短路径。路径上的第一个顶点为源点，最后一个顶点为终点。路径上的第一个顶点为源点，最后一个顶点为终点。问题的提出问

32、题的提出:7.5 7.5 最短路径最短路径第29页，本讲稿共99页30 最最最最短短短短路路路路径径径径问问问问题题题题：如如如如果果果果从从从从图图图图中中中中某某某某一一一一顶顶顶顶点点点点(源源源源点点点点)到到到到达达达达另另另另一一一一顶顶顶顶点点点点(终终终终点点点点)的的的的路路路路径径径径可可可可能能能能不不不不止止止止一一一一条条条条，如如如如何何何何找找找找到到到到一一一一条条条条路路路路径径径径使使使使沿沿沿沿此此此此路路路路径径径径上上上上各边上的权值总和达到最小。各边上的权值总和达到最小。各边上的权值总和达到最小。各边上的权值总和达到最小。第30页，本讲稿共99页31

33、 从一个源点到其他各点的最短路径从一个源点到其他各点的最短路径1.1.问题的提法：给定一个带权有向图问题的提法：给定一个带权有向图问题的提法：给定一个带权有向图问题的提法：给定一个带权有向图D D D D与源点与源点与源点与源点v v v v，求从，求从，求从，求从v v v v到到到到D D D D中其它顶点的最短路径。中其它顶点的最短路径。中其它顶点的最短路径。中其它顶点的最短路径。7.5 7.5 最短路径最短路径10101010长度长度长度长度最短路径最短路径最短路径最短路径 V2V2V2 V4V4V43030303050505050909090902.2.迪杰斯特拉算法（迪杰斯特拉算法

34、（迪杰斯特拉算法（迪杰斯特拉算法（DijkstraDijkstraDijkstraDijkstra）（1 1 1 1）基本思想基本思想 为求得这些最短路径，为求得这些最短路径，为求得这些最短路径，为求得这些最短路径，DijkstraDijkstraDijkstraDijkstra提出提出提出提出按路径长度的递增次序，逐步产生最短路按路径长度的递增次序，逐步产生最短路按路径长度的递增次序，逐步产生最短路按路径长度的递增次序，逐步产生最短路径径径径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一的算法。首先求出长度最短

35、的一条最短路径，再参照它求出长度次短的一的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依此类推，直到从顶点条最短路径，依此类推，直到从顶点条最短路径，依此类推，直到从顶点条最短路径，依此类推，直到从顶点v v v v到其它各顶点的最短路径全部求出为止。到其它各顶点的最短路径全部求出为止。到其它各顶点的最短路径全部求出为止。到其它各顶点的最短路径全部求出为止。第31页，本讲稿共99页32依据算法的基本思想把依据算法的基本思想把V V分成两组：分成两组：（1 1）S S：已求出最短路径的顶点的集合：已求出最短路径的顶点的集合（2 2）V-S=TV-S=T：尚未确定最短

36、路径的顶点集合：尚未确定最短路径的顶点集合 将将T T中顶点按如下规则加入到中顶点按如下规则加入到S S中：中：（1 1）按递增的次序产生最短路径：从源点）按递增的次序产生最短路径：从源点V V0 0到到S S中各顶点的最短中各顶点的最短路径长度都不大于从路径长度都不大于从V V0 0到到T T中任何顶点的最短路径长度中任何顶点的最短路径长度;（2 2）待求的最短路径最多以已求出最短路径的顶点为中间点：从）待求的最短路径最多以已求出最短路径的顶点为中间点：从V V0 0到某顶点的最短路径中，只将到某顶点的最短路径中，只将S S中的顶点作为中间点中的顶点作为中间点第32页，本讲稿共99页33（2

37、 2）Dijkstra Dijkstra 算法的基本步骤算法的基本步骤 设设设设V V V V0 0 0 0是是是是源源源源点点点点，初初初初使使使使时时时时令令令令S=VS=VS=VS=V0 0 0 0,T=,T=,T=,T=其其其其余余余余顶顶顶顶点点点点 ，T T T T中中中中顶顶顶顶点点点点对对对对应应应应的的的的距距距距离离离离值值值值若若若若存存存存在在在在，VVV,Vi,Vi,Vi边边边边权权权权值值值值为为为为VVV,Vi,Vi,Vi弧弧弧弧上上上上的的的的权权权权值值值值；若若若若不不不不存存存存在在在在，,Vi,Vi,Vi边权值为边权值为边权值为边权值为 。1 1 1 1

38、）从）从）从）从T T T T中选取一个其距离值最小的顶点中选取一个其距离值最小的顶点中选取一个其距离值最小的顶点中选取一个其距离值最小的顶点W W W W，加入，加入，加入，加入S S S S；2 2 2 2）对对对对T T T T中顶点的距离值进行修改：先求出中顶点的距离值进行修改：先求出中顶点的距离值进行修改：先求出中顶点的距离值进行修改：先求出V V V V0 0 0 0到到到到ViViViVi中间只经中间只经中间只经中间只经S S S S中中中中结点的最短路径；若加进结点的最短路径；若加进结点的最短路径；若加进结点的最短路径；若加进W W W W作中间顶点后从作中间顶点后从作中间顶点

39、后从作中间顶点后从V V V V0 0 0 0到到到到ViViViVi的距离值的距离值的距离值的距离值 比比比比 不加不加不加不加W W W W的路径要短，则修改此距离值；的路径要短，则修改此距离值；的路径要短，则修改此距离值；的路径要短，则修改此距离值；上上上上述述述述最最最最短短短短路路路路径径径径中中中中长长长长度度度度最最最最小小小小者者者者即即即即为为为为下下下下一一一一条条条条长长长长度度度度最最最最短短短短的的的的路路路路径；径；径；径；将所求最短路径的终点加入将所求最短路径的终点加入将所求最短路径的终点加入将所求最短路径的终点加入S S S S中；中；中；中；3 3 3 3）重

40、复）重复）重复）重复2 2 2 2）直到）直到）直到）直到S S S S中包含所有顶点，即中包含所有顶点，即中包含所有顶点，即中包含所有顶点，即S=VS=VS=VS=V为止。为止。为止。为止。7.5 7.5 最短路径最短路径第33页，本讲稿共99页34 1）图用带权邻接矩阵存储；）图用带权邻接矩阵存储；2 2）引入一个辅助数组引入一个辅助数组dist。它的每一个分量。它的每一个分量disti表示当前找到表示当前找到的从源点的从源点v0 到终点到终点vi 的最短路径的长度的最短路径的长度 初始状态：初始状态：若从源点若从源点v0 到顶点到顶点vi有边，则有边，则disti为该边上的权为该边上的权

41、值；值；若从源点若从源点v0 到顶点到顶点vi 没有边，则没有边，则disti为为 。3 3）数组）数组path表示从表示从V0到各终点的最短路径上，此顶点的到各终点的最短路径上，此顶点的前一前一顶点顶点的序号；若从的序号；若从V0 到某终点无路径，则用到某终点无路径，则用-1-1 作为该结点前一作为该结点前一顶点的序号顶点的序号4)4)数组数组s标识标识V0 到该结点的最短路径是否求出。到该结点的最短路径是否求出。0 0表示没求出，表示没求出，1 1表示已求出。表示已求出。7.5 7.5 最短路径最短路径(3)(3)算法实现算法实现第34页，本讲稿共99页357.5 7.5 最短路径最短路径

42、260003013501010122601030135010101439000301350001013010000300160001011010000300-1 001000P4d4S4P3d3S3P2d2S2P1d1S1顶点4顶点3顶点2顶点1选取点01234第35页，本讲稿共99页36 如何从表中读取源点如何从表中读取源点0 0到终点的最短路径？到终点的最短路径？以顶点以顶点4 4为例：为例：(1)V0 (1)V0到顶点到顶点4 4的最短路径为的最短路径为6060。(2)path4=2 path2=3 (2)path4=2 path2=3 path3=0 path3=0；反过来排列，得到路

43、径反过来排列，得到路径0,3,2,40,3,2,4，即，即V0V0到顶到顶点点V4V4的最短路径。的最短路径。7.5 7.5 最短路径最短路径2600030135010101226010301350101014390003013500010130100003001600010110100003000 001000P4d4S4P3d3S3P2d2S2P1d1S1顶点4顶点3顶点2顶点1选取点第36页，本讲稿共99页37 Dijkstra Dijkstra Dijkstra Dijkstra 算法的时间复杂度为算法的时间复杂度为O(n2)第37页，本讲稿共99页38 7.6 AOV7.6 AOV网

44、与拓扑排序网与拓扑排序第38页，本讲稿共99页397.6.1 7.6.1 有向无环图的概念有向无环图的概念1.1.有向无环图（有向无环图（directed acycline graphdirected acycline graph）：没有回路的有向图。：没有回路的有向图。含有公共子式的表达式含有公共子式的表达式 例如：表达式例如：表达式(a+b)*(a+b-e/f)(a+b)*(a+b-e/f)a a -+b b */e e f f 用用有向无环图有向无环图表示的表达式表示的表达式 流程图：流程图：工程流程、生产过程中工序流程、程序流程、课程的流程。工程流程、生产过程中工序流程、程序流程、课程

45、的流程。常用的两种有向无环图是：常用的两种有向无环图是：AOVAOV网，网，AOEAOE网。网。7.6 7.6 有向无环图及其应用有向无环图及其应用 -a a +b b */e e f f a a +b b 用用二叉树二叉树表示的表达式表示的表达式第39页，本讲稿共99页407.6.2 AOV AOV网与拓扑排序网与拓扑排序1.AOV1.AOV网网网网 (Activity On Vertex network)(Activity On Vertex network)用顶点表示用顶点表示用顶点表示用顶点表示活动活动，边表示边表示边表示边表示活动的顺序关系活动的顺序关系的有向图称为的有向图称为的有向

46、图称为的有向图称为AOVAOVAOVAOV网。网。网。网。在在在在AOVAOVAOVAOV网中，若从顶点网中，若从顶点网中，若从顶点网中，若从顶点i i i i到顶点到顶点到顶点到顶点j j j j有一条有向路径。则顶点有一条有向路径。则顶点有一条有向路径。则顶点有一条有向路径。则顶点i i i i是顶点是顶点是顶点是顶点j j j j的前驱，的前驱，的前驱，的前驱，j j j j是是是是i i i i的后继。若的后继。若的后继。若的后继。若是网中一条弧，则是网中一条弧，则是网中一条弧，则是网中一条弧，则i i i i是是是是j j j j的直接前驱，的直接前驱，的直接前驱，的直接前驱，j j

47、 j j是是是是i i i i的直接后继。的直接后继。的直接后继。的直接后继。在在在在AOVAOVAOVAOV网中，每一条弧表示了活动之间存在的制约关系。网中，每一条弧表示了活动之间存在的制约关系。网中，每一条弧表示了活动之间存在的制约关系。网中，每一条弧表示了活动之间存在的制约关系。注：注：注：注：AOVAOV网中不允许有回路，这意味着某项活动以自己为先网中不允许有回路，这意味着某项活动以自己为先决条件。决条件。例如：计算机专业的学生必须学习一系列的基本课和专业课。例如：计算机专业的学生必须学习一系列的基本课和专业课。例如：计算机专业的学生必须学习一系列的基本课和专业课。例如：计算机专业的学

48、生必须学习一系列的基本课和专业课。学生应按照怎样的顺序来学习呢？学生应按照怎样的顺序来学习呢？学生应按照怎样的顺序来学习呢？学生应按照怎样的顺序来学习呢？可以把这个问题看做一个大的可以把这个问题看做一个大的可以把这个问题看做一个大的可以把这个问题看做一个大的工程，其活动就是学习每一门课程。工程，其活动就是学习每一门课程。工程，其活动就是学习每一门课程。工程，其活动就是学习每一门课程。7.6 7.6 有向无环图及其应用有向无环图及其应用第40页，本讲稿共99页41C1C1C2C2C3C3C4C4C5C5C6C6C7C7C8C8C9C9C10C10C11C11无无无无无无无无C1,C2C1,C2C

49、3C3，C9C9C2C2C4C4C5C5C4C4C1C1C4C4，C9C9C4,C7C4,C7课程代号课程代号课程代号课程代号 课程名称课程名称课程名称课程名称 先修课先修课先修课先修课程序设计基础程序设计基础程序设计基础程序设计基础高等数学高等数学高等数学高等数学离散数学离散数学离散数学离散数学数据结构数据结构数据结构数据结构普通物理普通物理普通物理普通物理人工智能人工智能人工智能人工智能计算机原理计算机原理计算机原理计算机原理算法分析算法分析算法分析算法分析高级语言高级语言高级语言高级语言编译系统编译系统编译系统编译系统操作系统操作系统操作系统操作系统 C1 C1 C1 C1、C2C2C2

50、C2是独立于其它课程的基础课，而另一些课程必须在是独立于其它课程的基础课，而另一些课程必须在是独立于其它课程的基础课，而另一些课程必须在是独立于其它课程的基础课，而另一些课程必须在学完作为它的基础课后才能开始，即有先行课。先行条件规学完作为它的基础课后才能开始，即有先行课。先行条件规学完作为它的基础课后才能开始，即有先行课。先行条件规学完作为它的基础课后才能开始，即有先行课。先行条件规定了课程之间的优先关系。定了课程之间的优先关系。定了课程之间的优先关系。定了课程之间的优先关系。计算机专业的课程设置及其关系计算机专业的课程设置及其关系7.6 7.6 有向无环图及其应用有向无环图及其应用第41页