数据结构第七章-图.ppt

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

1、2022/11/291第第7 7章章 图图图是一种图是一种多对多多对多多对多多对多的结构关系，每个元素可以有零个或多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继个直接前趋；零个或多个直接后继。2【重点掌握重点掌握】：1.1.图的两种遍历方法：遍历的定义、深度优先搜索遍历和图的两种遍历方法：遍历的定义、深度优先搜索遍历和广度优先搜索遍历的算法；广度优先搜索遍历的算法；2.2.应用图的遍历算法判断图的连通性及求图的生成树；应用图的遍历算法判断图的连通性及求图的生成树；3.3.用用PrimPrim、KruskalKruskal算法求图的最小生成树；算法求图的最小生成树；4.4.用

2、用DijkstraDijkstra算算法法求求解解单单源源最最短短路路径径问问题题；用用FloydFloyd算算法法求求所有顶点间的最短路径问题；所有顶点间的最短路径问题；5.5.利用利用AOVAOV网进行拓扑排序；利用网进行拓扑排序；利用AOEAOE网求关键路径问题；网求关键路径问题；【掌掌 握握】：1.1.掌握图的定义和术语；掌握图的定义和术语；2.2.图图的的各各种种存存储储结结构构及及其其构构造造算算法法、在在实实际际问问题题中中的的求求解解效率。效率。37.3 7.3 图的遍历图的遍历 7.3 7.3 图的遍历：图的遍历：从图的某顶点出发，访问图中所有顶点，从图的某顶点出发，访问图中

3、所有顶点，并且每个顶点仅访问一次。并且每个顶点仅访问一次。图结构的遍历复杂性：图结构的遍历复杂性：（1 1）在图结构中，没有一个）在图结构中，没有一个“自然自然”的首结点，图中的任的首结点，图中的任意一个顶点都可以作为第一个被访问的结点意一个顶点都可以作为第一个被访问的结点（2 2）在非连通图中，从一个顶点出发，只能访问它所在的）在非连通图中，从一个顶点出发，只能访问它所在的连通分量上的所有顶点，因此，还需考虑连通分量上的所有顶点，因此，还需考虑如何选取下一个出如何选取下一个出发点发点以访问图中的其余连通分量以访问图中的其余连通分量（3 3）在图结构中，如果有回路存在，那么一个顶点被访问）在图

4、结构中，如果有回路存在，那么一个顶点被访问后，有可能沿回路又回到该顶点，考虑后，有可能沿回路又回到该顶点，考虑如何避免重复访问如何避免重复访问（4 4）在图结构中，一个顶点可以和其他多个顶点邻接，当）在图结构中，一个顶点可以和其他多个顶点邻接，当这样的顶点访问过后，考虑这样的顶点访问过后，考虑如何选取下一个要访问的顶点的如何选取下一个要访问的顶点的问题问题4 图的遍历方法有深度优先遍历和广度优先遍历两种。图的遍历方法有深度优先遍历和广度优先遍历两种。深度优先搜索深度优先搜索方法：方法：（1 1）从图的某一顶点）从图的某一顶点V V0 0出发，访问此顶点；出发，访问此顶点；（2 2）依次从）依次

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

6、先序列不是唯一的 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4 V0,V1,V3,V4,V7,V2,V5,V6,V0,V1,V3,V4,V7,V2,V5,V6,求图求图G以以V0为起点的的深度优先序列（设存储结构为邻接为起点的的深度优先序列（设存储结构为邻接矩阵）矩阵）6void DFS(Graph G,int v)/*从第从第v个顶点出发，递归地深度优先遍历图个顶点出发，递归地深度优先遍历图G*/*v是顶点在一维数组中的位置，假设是顶点在一维数组中的位置，假设G是非空图是非空图*/visitedv=1;Visit(v);/*访问第访问第v个顶点个顶点*/fo

7、r(w=FirstAdjVex(G,v);w;w=NextAdjVex(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 图的遍历图的遍历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 图的遍历图的遍历9 在遍历时，

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

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

11、w1 1,w,w2 2,w,wk k ；3 3）依次从这些邻接点出发，访问它们的所有未被访问的邻）依次从这些邻接点出发，访问它们的所有未被访问的邻接点接点;依此类推，直到图中所有访问过的顶点的邻接点依此类推，直到图中所有访问过的顶点的邻接点都被访问；都被访问；广度优先遍历广度优先遍历7.3 7.3 图的遍历图的遍历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 V4V4若图的存储结构为邻接表，

12、则若图的存储结构为邻接表，则访问邻接点的顺序不唯一，访问邻接点的顺序不唯一，深度优先序列不是唯一的深度优先序列不是唯一的求图求图G以以V0为起点的的广度优先序列（设存储结构为邻为起点的的广度优先序列（设存储结构为邻接矩阵）接矩阵）先被访问的顶点，其先被访问的顶点，其邻接点也要先被访问邻接点也要先被访问设一队列保存已访问设一队列保存已访问的顶点的顶点12Q 在邻接表存储结构上的广度优先搜索在邻接表存储结构上的广度优先搜索V0V0V1V1V2V2V3V3V4V4V7V7V5V5V6V6V1V1V2V2V3V3V0V0V4V4V7V7V5V5V6V6 V0 V0 V7 V7 V6 V6 V5 V5

13、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 613void BFSTraverse(MGraph G)/*从从v出发，广度优先遍历连通图出发，广度优先遍历连通图G*/*使用辅助队列使用辅助队列Q和访问标志数组和访问标志数组visited*/for(v=0;vG.vexnum;+i)visitedv=0;InitQueue(Q,G.vexnum);/*初始化空的辅助队列初始化空的辅助队列Q*/for(

14、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*/*BFSTraverse*/7.3 7.3 图的遍历图的遍历14第七 章 图 7.

15、4 连通网的最小生成树连通网的最小生成树 7.4.1 生成树生成树 7.4.2 最小生成树最小生成树 7.4.3 构造最小生成树的构造最小生成树的Prim算法算法 7.4.4 构造最小生成树的构造最小生成树的Kruskal算法算法15 生成树生成树生成树：生成树：包含了无向图包含了无向图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 最小的生成树最小的生成树167.4 7.4 最小的生成树最小的生成树 生成树的含义：生成树的含义：生成树的含义：生成树的含义：n n个个顶点的图顶点的图最多可存在最多可存在n(n-1)/2n(n-1)/2条边条边

17、线路。求生成树是为了在网络中连通线路。求生成树是为了在网络中连通n n个顶点而选择最少的个顶点而选择最少的边边(n(n1)1)。例如：一个通信网络中，节点代表了路由器，为了使例如：一个通信网络中，节点代表了路由器，为了使各路由器之间是连通的（数据可达），且不形成回路各路由器之间是连通的（数据可达），且不形成回路(数据数据回到发送方回到发送方)，则需建立该网络的生成树。，则需建立该网络的生成树。17求生成树的方法：求生成树的方法：求生成树的方法：求生成树的方法：利用遍历算法。利用遍历算法。从连通图中的任一顶点出发进行遍历时，除出发从连通图中的任一顶点出发进行遍历时，除出发点外，其余顶点必须通过一

18、条边才能到达，所以遍历点外，其余顶点必须通过一条边才能到达，所以遍历过程中经历的边有过程中经历的边有n-1n-1条，它和条，它和n n个顶点组成了连通图个顶点组成了连通图的一棵生成树。的一棵生成树。由深度优先搜索得到的是深度优先生成树；由广度由深度优先搜索得到的是深度优先生成树；由广度优先搜索得到的是广度优先生成树。优先搜索得到的是广度优先生成树。18 V0 V0 V7 V7 V6 V6 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 V1

19、7.4 7.4 最小的生成树最小的生成树 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1深度优先搜索生成树深度优先搜索生成树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 V6 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

20、 V120 最小生成树的概念最小生成树的概念 由生成树的定义可知，无向连通图的生成树不是惟一由生成树的定义可知，无向连通图的生成树不是惟一的。的。问题的提出：问题的提出：设要在设要在n n个城市间建立通信联络网，顶点个城市间建立通信联络网，顶点表示城市，权表示城市间建立通信线路所需花费代价。表示城市，权表示城市间建立通信线路所需花费代价。希望找到一棵生成树，它的每条边上的权值之和（即建立希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小该通信网所需花费的总代价）最小最小代价生成树。最小代价生成树。7.4 7.4 最小的生成树最小的生成树21 最小生成树定义：最小生

21、成树定义：对于一个网络，它的所有生成树对于一个网络，它的所有生成树中边权值最小的生成树称为最小生成树。中边权值最小的生成树称为最小生成树。问题分析：问题分析：n n个城市间建立通信网，如何在可能的线路个城市间建立通信网，如何在可能的线路中选择中选择n-1n-1条，能把所有城市（顶点）均连起来，且总条，能把所有城市（顶点）均连起来，且总耗费（各边权值之和）最小。耗费（各边权值之和）最小。即：如何在保证即：如何在保证n点连通点连通的前题下最节省经费的前题下最节省经费?221.1.Prim 法基本步骤法基本步骤 设连通网络设连通网络设连通网络设连通网络G=V,E。集合。集合。集合。集合U存放存放存放

22、存放G的最小生成树中的的最小生成树中的的最小生成树中的的最小生成树中的顶点，集合顶点，集合顶点，集合顶点，集合T存放最小生成树之外的顶点。存放最小生成树之外的顶点。存放最小生成树之外的顶点。存放最小生成树之外的顶点。(1)从从从从G中选择某一顶点中选择某一顶点中选择某一顶点中选择某一顶点u u u u0 0 0 0出发，在与它关联的边中选择一个出发，在与它关联的边中选择一个出发，在与它关联的边中选择一个出发，在与它关联的边中选择一个边权最小的边边权最小的边边权最小的边边权最小的边(u(u(u(u0 0 0 0,v);,v);,v);,v);将顶点将顶点将顶点将顶点v v v v加入最小生成树的

23、加入最小生成树的加入最小生成树的加入最小生成树的顶点集顶点集顶点集顶点集合合合合U U U U，在，在，在，在集合集合集合集合T T T T 中删除该顶点；中删除该顶点；中删除该顶点；中删除该顶点；(2)用顶点用顶点用顶点用顶点v v v v到集合到集合到集合到集合T T T T中顶点的边权中顶点的边权中顶点的边权中顶点的边权“更新更新更新更新”原集合原集合原集合原集合U U U U中顶点到中顶点到中顶点到中顶点到集合集合集合集合T T T T中顶点的最小边权；中顶点的最小边权；中顶点的最小边权；中顶点的最小边权；(3)从一个顶点在从一个顶点在从一个顶点在从一个顶点在U中，而另一个顶点在中，而

24、另一个顶点在中，而另一个顶点在中，而另一个顶点在T T T T中的各条边中选择中的各条边中选择中的各条边中选择中的各条边中选择权值最小的边权值最小的边权值最小的边权值最小的边(u,v),把顶点把顶点把顶点把顶点v v v v加入到加入到加入到加入到集合集合集合集合U U U U 中。中。中。中。(4)重复重复重复重复(2)、(3)，直到网络中的所有顶点都加入到生成树，直到网络中的所有顶点都加入到生成树，直到网络中的所有顶点都加入到生成树，直到网络中的所有顶点都加入到生成树顶点集合顶点集合顶点集合顶点集合U中为止。中为止。中为止。中为止。构造最小生成树的构造最小生成树的PrimPrim算法算法7

25、.4 7.4 最小的生成树最小的生成树23V3V3V1V1V4V4V6V6V5V5V2V2651U=V1 V3V3V1V1V4V4V6V6V5V5V2V251654V3V3V4V4V6V6V5V5V2V21V1V1U=V1,V3 U=V1,V3 V3V3V1V1V4V4V6V6V5V5V2V216542V3V3V1V1V4V4V6V6V5V5V2V251654U=V1,V3,V6U=V1,V3,V67.4 7.4 最小的生成树最小的生成树V3V3V1V1V4V4V6V6V5V5V2V236521655462.2.过程演示过程演示24V3V3V1V1V4V4V6V6V5V5V2V216542U=

26、V1,V3,V6,V4U=V1,V3,V6,V4 V3V3V1V1V4V4V6V6V5V5V2V216542U=V1,V3,V6,V4,V2 U=V1,V3,V6,V4,V2 V3V3V1V1V4V4V6V6V5V5V2V215423U=V1,V3,V6,V4,V2,V5 U=V1,V3,V6,V4,V2,V5 7.4 7.4 最小的生成树最小的生成树V3V3V1V1V4V4V6V6V5V5V2V23652165546Prim 算法的时间复杂度为算法的时间复杂度为O(n2)257.4.3 7.4.3 构造最小生成树的构造最小生成树的KruskalKruskal算法算法1.1.基本思想：按网中权

27、值递增的顺序构造最小生成树。基本思想：按网中权值递增的顺序构造最小生成树。2.2.基本步骤基本步骤 1 1）设连通网）设连通网G=(V,E)G=(V,E)，令最小生成树初始状态是只有，令最小生成树初始状态是只有n n个个顶点而无边的非连通图顶点而无边的非连通图T=(V,T=(V,)，每个顶点自成一个连，每个顶点自成一个连通分量；通分量；2 2）在）在E E中选取代价最小的边，若该边依附的顶点落在中选取代价最小的边，若该边依附的顶点落在T T中中不同的连通分量上，则将此边加入到不同的连通分量上，则将此边加入到T T中；否则，舍去中；否则，舍去此边，选取下一条代价最小的边；此边，选取下一条代价最小

28、的边；3 3）依此类推，直至）依此类推，直至T T中所有顶点都在同一连通分量上为中所有顶点都在同一连通分量上为止。止。7.4 7.4 最小的生成树最小的生成树26V3V3V1V1V4V4V6V6V5V5V2V2V3V3V4V4V6V6V5V5V2V21V1V1V3V3V1V1V4V4V6V6V5V5V2V212V3V3V1V1V4V4V6V6V5V5V2V2123V3V3V1V1V4V4V6V6V5V5V2V2164237.4 7.4 最小的生成树最小的生成树V3V3V1V1V4V4V6V6V5V5V2V236521655463.3.过程演示过程演示27V3V3V1V1V4V4V6V6V5V5

29、V2V2165423V3V3V1V1V4V4V6V6V5V5V2V236521655467.4 7.4 最小的生成树最小的生成树Kruskal 算法的时间复杂度为算法的时间复杂度为O(ne)。28 7.5 7.5 单源最短路径单源最短路径(Shortest Path)(Shortest Path)从一个源点到其他各点的最短路径从一个源点到其他各点的最短路径29 交交通通咨咨询询系系统统、通通讯讯网网、计计算算机机网网络络中中经经常常要要寻寻找找两两结结点点间间最最短短路路径径。例例如如：交交通通咨咨询询系系统统中中：咨咨询询A A到到B B的的最最短短路路径径；计计算算机机网网中中如如何何发发

30、送送E-mailE-mail才才最最节节省省费费用用（使使E-mailE-mail由由A A到到B B沿最短路径传送）。沿最短路径传送）。设用带权的有向图表示一个交通运输网，图中：设用带权的有向图表示一个交通运输网，图中：顶点顶点表示城市表示城市 边边表示城市间的交通联系表示城市间的交通联系 权权表示此线路的长度或沿此线路运输所花的时间表示此线路的长度或沿此线路运输所花的时间或费用等或费用等 这类问题归结为从某顶点出发，沿图的边到达另一顶点这类问题归结为从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径所经过的路径中，各边上权值之和最小的一条路径最短最短路径。路径上

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

32、值总和达到最小。沿此路径上各边上的权值总和达到最小。31 从一个源点到其他各点的最短路径从一个源点到其他各点的最短路径1.1.问题的提法：给定一个带权有向图问题的提法：给定一个带权有向图问题的提法：给定一个带权有向图问题的提法：给定一个带权有向图D D D D与源点与源点与源点与源点v v v v，求从，求从，求从，求从v v v v到到到到D D D D中其它顶点中其它顶点中其它顶点中其它顶点的最短路径。的最短路径。的最短路径。的最短路径。7.5 7.5 最短路径最短路径10101010长度长度长度长度最短路径最短路径最短路径最短路径 V2V2V2 V4V4V4303030305050505

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

34、的算法。首先求出长度最短的一条最短路径，再参照它的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依此类推，直到从顶点求出长度次短的一条最短路径，依此类推，直到从顶点求出长度次短的一条最短路径，依此类推，直到从顶点求出长度次短的一条最短路径，依此类推，直到从顶点v v v v到其它各顶点到其它各顶点到其它各顶点到其它各顶点的最短路径全部求出为止。的最短路径全部求出为止。的最短路径全部求出为止。的最短路径全部求出为止。32依据算法的基本思想把依据算法的基本思想把V V分成两组：分成两组：（1 1）S S：已求出最短路径的顶点的集合：已求出最短路径的顶点的集合（2 2）V

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

36、33（2 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边权值为边权值为边权值为边权值为 。

37、1 1 1 1）从）从）从）从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作中间顶点后从作中间顶点

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

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

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

41、2601030135010101439000301350001013010000300160001011010000300-1 001000P4d4S4P3d3S3P2d2S2P1d1S1顶点4顶点3顶点2顶点1选取点0123436 如何从表中读取源点如何从表中读取源点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；反过来排列，得到路径反过来排列，得到路径0,3,2,40,3,2,4，即，即V

42、0V0到顶点到顶点V4V4的最短路径。的最短路径。7.5 7.5 最短路径最短路径2600030135010101226010301350101014390003013500010130100003001600010110100003000 001000P4d4S4P3d3S3P2d2S2P1d1S1顶点4顶点3顶点2顶点1选取点37 Dijkstra Dijkstra Dijkstra Dijkstra 算法的时间复杂度为算法的时间复杂度为O(n2)38 7.6 AOV7.6 AOV网与拓扑排序网与拓扑排序397.6.1 7.6.1 有向无环图的概念有向无环图的概念1.1.有向无环图（有向无

43、环图（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 用用有向无环图有向无环图表示的表达式表示的表达式 流程图：流程图：工程流程、生产过程中工序流程、程序流程、课程的流工程流程、生产过程中工序流程、程序流程、课程的流程。常用的两种有向无环图是：程。常用的两种有向无环图是：AOVAOV网，网，AOEAOE网。网。7.6 7.6 有向无环图及其应用有

44、向无环图及其应用 -a a +b b */e e f f a a +b b 用用二叉树二叉树表示的表达式表示的表达式40 AOV AOV网与拓扑排序网与拓扑排序1.AOV1.AOV网网网网 (Activity On Vertex network)(Activity On Vertex network)用顶点表示用顶点表示用顶点表示用顶点表示活动活动，边表示边表示边表示边表示活动的顺序关系活动的顺序关系的有向图称为的有向图称为的有向图称为的有向图称为AOVAOVAOVAOV网。网。网。网。在在在在AOVAOVAOVAOV网中，若从顶点网中，若从顶点网中，若从顶点网中，若从顶点i i i i到顶点

45、到顶点到顶点到顶点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 j j是是是是i i i i的直接后继。的直接后继。的直接后继。的直接后继。在在在在AOVAOVAOVAOV网中，每一条弧表示了活动之间存在的制约关系。网中，每一条

46、弧表示了活动之间存在的制约关系。网中，每一条弧表示了活动之间存在的制约关系。网中，每一条弧表示了活动之间存在的制约关系。注：注：注：注：AOVAOV网中不允许有回路，这意味着某项活动以自己为网中不允许有回路，这意味着某项活动以自己为先决条件。先决条件。例如：计算机专业的学生必须学习一系列的基本课和专例如：计算机专业的学生必须学习一系列的基本课和专例如：计算机专业的学生必须学习一系列的基本课和专例如：计算机专业的学生必须学习一系列的基本课和专业课。学生应按照怎样的顺序来学习呢？业课。学生应按照怎样的顺序来学习呢？业课。学生应按照怎样的顺序来学习呢？业课。学生应按照怎样的顺序来学习呢？可以把这个问

47、可以把这个问可以把这个问可以把这个问题看做一个大的工程，其活动就是学习每一门课程。题看做一个大的工程，其活动就是学习每一门课程。题看做一个大的工程，其活动就是学习每一门课程。题看做一个大的工程，其活动就是学习每一门课程。7.6 7.6 有向无环图及其应用有向无环图及其应用41C1C1C2C2C3C3C4C4C5C5C6C6C7C7C8C8C9C9C10C10C11C11无无无无无无无无C1,C2C1,C2C3C3，C9C9C2C2C4C4C5C5C4C4C1C1C4C4，C9C9C4,C7C4,C7课程代号课程代号课程代号课程代号 课程名称课程名称课程名称课程名称 先修课先修课先修课先修课程序

48、设计基础程序设计基础程序设计基础程序设计基础高等数学高等数学高等数学高等数学离散数学离散数学离散数学离散数学数据结构数据结构数据结构数据结构普通物理普通物理普通物理普通物理人工智能人工智能人工智能人工智能计算机原理计算机原理计算机原理计算机原理算法分析算法分析算法分析算法分析高级语言高级语言高级语言高级语言编译系统编译系统编译系统编译系统操作系统操作系统操作系统操作系统 C1 C1 C1 C1、C2C2C2C2是独立于其它课程的基础课，而另一些课程必须是独立于其它课程的基础课，而另一些课程必须是独立于其它课程的基础课，而另一些课程必须是独立于其它课程的基础课，而另一些课程必须在学完作为它的基础

49、课后才能开始，即有先行课。先行条在学完作为它的基础课后才能开始，即有先行课。先行条在学完作为它的基础课后才能开始，即有先行课。先行条在学完作为它的基础课后才能开始，即有先行课。先行条件规定了课程之间的优先关系。件规定了课程之间的优先关系。件规定了课程之间的优先关系。件规定了课程之间的优先关系。计算机专业的课程设置及其关系计算机专业的课程设置及其关系7.6 7.6 有向无环图及其应用有向无环图及其应用42 顶点表示课程，弧表示前提条件活动。若课程顶点表示课程，弧表示前提条件活动。若课程i i是课程是课程j j的先行课，的先行课，则必然存在弧则必然存在弧。由此得到如下。由此得到如下AOVAOV网：

50、网：在安排学习顺序时，必须保证在学习某门课前，已经学习了其先行课。在安排学习顺序时，必须保证在学习某门课前，已经学习了其先行课。如何设置这些课程的学习顺序，才能无矛盾、顺利地完成学业？如何设置这些课程的学习顺序，才能无矛盾、顺利地完成学业？7.6 7.6 有向无环图及其应用有向无环图及其应用C1程序设计基础程序设计基础程序设计基础程序设计基础C3离散数学离散数学离散数学离散数学C2高等数学高等数学高等数学高等数学C4数据结构数据结构数据结构数据结构C5普通物理普通物理普通物理普通物理C6人工智能人工智能人工智能人工智能C7计算机原理计算机原理计算机原理计算机原理C8算法分析算法分析算法分析算法