数据结构第7章最新图.ppt

第7章图,7.1图的定义与基本术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图的应用7.6最短路径,图是一种较线性表和树更为复杂的数据结构。线性结构是研究数据元素之间的一对一关系。在这种结构中，除第一个和最后一个元素外，任何一个元素都有唯一的一个直接前驱和直接后继。树结构是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。,图结构是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。图的应用极为广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。因此十分重要。,1.图的定义,G1=V1=v0,v1,v2,v3,v4E1=(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4),图G由两个集合构成，记作G=其中:V（vertex）是顶点的非空有限集合E（edge）是边的有限集合，而边是顶点对的集合。,例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图，如产品的生产流程图顶点：工序边：各道工序之间的顺序关系,图的应用举例,2.图的基本术语,弧(Arc)：表示两个顶点v和w之间存在关系，用顶点偶对表示。通常根据图的顶点偶对将图分为有向图和无向图。有向图(Digraph)：若图的关系集合E(G)中，顶点偶对的v和w之间是有序的，称图G是有向图。在有向图中，若E(G)，表示从顶点v到顶点w有一条弧。其中：v称为弧尾(tail)或始点(initialnode)，w称为弧头(head)或终点(terminalnode)。无向图(Undigraph)：若图G的关系集合E(G)中，顶点偶对的v和w之间是无序的，称G是无向图，用(v,w)表示。,在无向图中，用无序对(v,w)表示v和w之间的一条边(Edge)，因此，(v,w)和(w,v)代表的是同一条边。设有向图G1和无向图G2，如图7.1所示，形式化定义分别是：G1=(V1，E1)V1=a,b,c,d,eE1=,，,G2=(V2，E2)V2=a,b,c,dE2=(a,b),(a,c),(a,d),(b,d),(b,c),(c,d),完全无向图：对于无向图，若图中顶点数为n，用e表示边的数目，则e0，n(n-1)/2。具有n(n-1)/2条边的无向图称为完全无向图。完全无向图另外的定义是：对于无向图G=(V，E)，若vi，vjV，当vivj时，有(vi,vj)E，即图中任意两个不同的顶点间都有一条无向边，这样的无向图称为完全无向图。,完全有向图：对于有向图，若图中顶点数为n，用e表示边或者弧的数目，则e0，n(n-1)。具有n(n-1)条边的有向图称为完全有向图。完全有向图另外的定义是：对于有向图G=(V，E)，若，vi，vjV，当，vivj时，有EE。即图中任意两个不同的顶点间都有一条边或者弧，这样的有向图称为完全有向图。v有很少边或弧(enext=r-next;r-next=p;r=p;,3.删除,在链表中删除某元素的示意图如下：,删除步骤（即核心语句）：,q=p-next;/保存b的指针，靠它才能指向cp-next=q-next;/a、c两结点相连free(q)；/删除b结点，彻底释放,p-next,思考：省略free(q)语句行不行？,(p-next)-next,/删除操作StatusListDelete_L(LinkList,在链表中插入一个元素的示意图如下：,插入步骤（即核心语句）：,Step1：s-next=p-next;Step2：p-next=s；,p-next,s-next,元素x结点应预先生成：s=(LinkList)malloc(sizeof(LNode);s-data=x;s-next=p-next;p-next=s;,StatusListInsert_L(LinkList,循环执行的结束条件分别是什么？如果在p不为空的情况下结束循环，j的值为多少？循环执行了多少次？P指针指向那个元素？,循环执行的结束条件分别是什么？P为空或者j=i-1.如果在p不为空的情况下结束循环，j的值为多少？为i-1.循环执行了多少次？i-1次。P指针指向那个元素？第i-1个元素。,7.2.3十字链表法十字链表(OrthogonalList)(List)是有向图的另一种链式存储结构，是将有向图的正邻接表和逆邻接表结合起来得到的一种链表。在这种结构中，每条弧的弧头结点和弧尾结点都存放在链表中，并将弧结点分别组织到以弧尾结点为头(顶点)结点和以弧头结点为头(顶点)结点的链表中。,图7.11图的十字链表弧结点、顶点结点结构图,图7.12图7.1中有向图G1的十字链表,可以看到，弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。在十字链表中既容易找到以顶点i为尾的弧，也容易找到以顶点i为头的弧，易求入度和出度。建立十字链表的复杂度同邻接表。,图的十字链表结构形式化定义如下：,defineMAX_VERTEX_NUM10/*最多顶点个数*/typedefenumDG,DN,UDG,UDNGraphKind;/*图的种类*/typedefstructArcBoxinttailvex,headvex;structArcBox*hlink,*tlink;InfoType*info;ArcBox;typedefstructVexNodeVertexTypedata;/*顶点信息*/ArcBox*firstin,*firstout;VexNode;typedefstructVexNodexlistMAX_VERTEX_NUM;intvexnum,arcnum;/*图的顶点数和弧数*/OLGraph;/*图的十字链表表示法(OrthogonalList)*/,7.2.4邻接多重表,图7.13邻接多重表的结点结构,邻接多重表的结构类型说明如下：,typedefemnuunvisited,visitedVisitIf;typedefstructEBoxVisitIfmark;intivex,jvex;structEbox*ilink,*jlink;InfoType*Info;EBox;typedefstructVerBoxVertexTypedata;Ebox*firstedge;VexBox;typedefstructVexBoxadjmulistMAX_VERTEX_NUM;intvexnum,arcnum;/*图的顶点数和弧数*/AMLGraph;/*基于图的邻接多重表表示法(AdjacencyMulti-list)*/,图7.14无向图的邻接多重表表示,总结,图的几种存储结构：邻接矩阵、邻接表、十字链表和邻接多重表。每种存储结构都有各自的优缺点，而其本质区别就是节点里面包含的指针不同，注意区分。,7.3图的遍历,从图中某一顶点出发访问图中每一个结点，且每个顶点仅被访问一次。图的遍历是图的连通性问题、拓扑排序、求关键路径等的基础。图的遍历比起树的遍历要复杂得多。因为图中顶点关系是任意的，即图中顶点之间是多对多的关系，图可能是非连通图，图中还可能有回路存在，因此在访问了某个顶点后，可能沿着某条路径搜索后又回到该顶点上。为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，因此我们为图设置一个访问标志数组visitedn，用于标示图中每个顶点是否被访问过，它的初始值为0(“假”)，表示顶点均未被访问；一旦访问过顶点vi，则置访问标志数组中的visitedi为1(“真”)，以表示该顶点已访问。,7.3.1深度优先搜索深度优先搜索（Depth-FirstSearch）是指按照深度方向搜索，它类似于树的先根遍历，是树的先根遍历的推广。深度优先搜索连通子图的基本思想是：（1）从图中某个顶点v0出发，首先访问v0。（2）找出刚访问过的顶点vi的第一个未被访问的邻接点，然后访问该顶点。以该顶点为新顶点，重复本步骤，直到当前的顶点没有未被访问的邻接点为止。（3）返回前一个访问过的且仍有未被访问的邻接点的顶点，找出并访问该顶点的下一个未被访问的邻接点，然后执行步骤(2)。,采用递归的形式说明，则深度优先搜索连通子图的基本思想可表示为：（1）访问出发点v0。（2）依次以v0的未被访问的邻接点为出发点，深度优先搜索图，直至图中所有与v0有路径相通的顶点都被访问。若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直至图中所有顶点均被访问过为止。图7.15给出了一个深度优先搜索的过程图示，其中实箭头代表访问方向，虚箭头代表回溯方向，箭头旁边的数字代表搜索顺序，A为起始顶点。,图7.15图的深度优先搜索过程图示,首先访问A，然后按图中序号对应的顺序进行深度优先搜索。图中序号对应步骤的解释如下：（1）顶点A的未访邻接点有B、E、D，首先访问A的第一个未访邻接点B；（2）顶点B的未访邻接点有C、E，首先访问B的第一个未访邻接点C；（3）顶点C的未访邻接点只有F，访问F；（4）顶点F没有未访邻接点，回溯到C；（5）顶点C已没有未访邻接点，回溯到B；,（6）顶点B的未访邻接点只剩下E，访问E；（7）顶点E的未访邻接点只剩下G，访问G；（8）顶点G的未访邻接点有D、H，首先访问G的第一个未访邻接点D；（9）顶点D没有未访邻接点，回溯到G；（10）顶点G的未访邻接点只剩下H，访问H；（11）顶点H的未访邻接点只有I，访问I；（12）顶点I没有未访邻接点，回溯到H；（13）顶点H已没有未访邻接点，回溯到G；（14）顶点G已没有未访邻接点，回溯到E；（15）顶点E已没有未访邻接点，回溯到B；（16）顶点B已没有未访邻接点，回溯到A。,BooleanvisitedMAX;Status(*visitFunc)(intv);/是对节点元素执行相应的操作voidDFSTraverse(GraphG,Status(*visit)(intv)/*对图G进行深度优先搜索，Graph表示图的一种存储结构*/VisitFunc=Visit;for(v=0;v=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/*递归调用DFS*/*DFS*/,7.3.2广度优先搜索,广度优先搜索（Breadth-FirstSearch）是指照广度方向搜索，它类似于树的层次遍历，是树的按层次遍历的推广。广度优先搜索的基本思想是：（1）从图中某个顶点v0出发，首先访问v0。（2）依次访问v0的各个未被访问的邻接点。（3）分别从这些邻接点（端结点）出发，依次访问它们的各个未被访问的邻接点（新的端结点）。访问时应保证：如果vi和vk为当前端结点，vi在vk之前被访问，则vi的所有未被访问的邻接点应在vk的所有未被访问的邻接点之前访问。重复（3），直到所有端结点均没有未被访问的邻接点为止。,图7.16图的广度优先搜索过程图示,广度优先搜索连通子图的算法如下：,voidBFSTraverse(GraphG,Status(*Visit)(intv)/*广度优先搜索图G*/for(v=0;v=0;w=NextAdjVex(G,u,w)if(!visitedw)Visit(w);visitedw=True;EnQueue(Q,w);/if/while/if/BFSTraverse,分析上述算法，图中每个顶点至多入队一次，因此外循环次数为n。当图g采用邻接表方式存储，则当结点v出队后，内循环次数等于结点v的度。由于访问所有顶点的邻接点的总的时间复杂度为O(d0+d1+d2+dn-1)=O(e)，因此图采用邻接表方式存储，广度优先搜索算法的时间复杂度为O(n+e)；当图g采用邻接矩阵方式存储，由于找每个顶点的邻接点时，内循环次数等于n，因此广度优先搜索算法的时间复杂度为O(n2)。,课堂练习,1无向图G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是（）。Aa,b,e,c,d,fBa,c,f,e,b,dCa,e,b,c,f,dDa,e,d,f,c,b,2、设下图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（）aebdfcacfdebaedfcbaefdcbaefdbcA5个B4个C3个D2个,3下面的邻接表表示一个给定的无向图（1）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列；（2）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。,7.4图的连通性问题,7.4.1无向图的连通分量,图遍历时，对于连通图，无论是广度优先搜索还是深度优先搜索，仅需要调用一次搜索过程，即从任一个顶点出发，便可以遍历图中的各个顶点。对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰为各连通分量中的顶点集。例如，图7.17(a)是一个非连通图，按照它的邻接表进行深度优先搜索遍历，三次调用DFSTraverse过程得到的访问顶点序列为：,1，2，4，3，95，6，78，10,图7.17图及其连通分量,1，2，4，3，95，6，78，10,设E(G)为连通图G中所有边的集合，则从图中任一顶点出发遍历图时，将E(G)分成两个集合T(G)和B(G)。T(G)为遍历时的边的集合，B(G)是剩余边的集合。显然，T(G)和G中所有顶点一起构成连通图G的极小连通子图，且为一棵生成树，按图的遍历方法不同，分别称为深度优先生成树和广度优先生成树。生成树的概念：若T是G的生成树当且仅当T满足如下条件：T是G的连通子图T包含G的所有顶点T中无回路对于非连通图，每个连通分量的顶点集和走过的边集一起构成若干生成树，称为生成森林。,7.4.2最小生成树,假设要在n个城市之间建立通信联络网，则联通n个城市只需要n-1条线路，这时自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树（MinimumCostSpanningTree），简称为最小生成树(MST)。最小生成树有如下重要性质：设N=(V,E)是一连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值的边，其中uU，vV-U，则存在一棵包含边（u,v）的最小生成树。,我们用反证法来证明这个MST性质：假设不存在这样一棵包含边（u,v）的最小生成树。任取一棵最小生成树T，将（u,v）加入T中。根据树的性质，此时T中必形成一个包含（u,v）的回路，且回路中必有一条边（u,v）的权值大于或等于（u,v）的权值。删除（u,v），则得到一棵代价小于等于T的生成树T，且T为一棵包含边（u,v）的最小生成树。这与假设矛盾，故该性质得证。我们可以利用MST性质来生成一个连通网的最小生成树。普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法便是利用了这个性质。,1.普里姆算法假设N=(V,E)是连通网，TE为最小生成树中边的集合。（1）初始U=u0(u0V),TE=；（2）在所有uU,vV-U的边（u,v）E中选一条代价最小的边（u0，v0）并入集合TE，同时将v0并入U；（3）重复（2），直到U=V为止。此时，TE中必含有n-1条边，则T=（V，TE）为N的最小生成树。可以看出，普利姆算法逐步增加U中的顶点，可称为“加点法”。,为了实现这个算法需要设置一个辅助数组closedge，以记录从U到V-U具有最小代价的边。对每个顶点vV-U，在辅助数组中存在一个分量closedgev，它包括两个域vex和lowcost，其中lowcost存储该边上的权，显然有closedgev.lowcost=Min(cost(u,v)|uU)普里姆算法可描述如下：structVertexTypeadjvex;VRTypelowcost;closedgeMAX_VERTEX_NUM;/*求最小生成树时的辅助数组*/,图7.18普里姆算法构造最小生成树的过程,表7-1普里姆算法各参量的变化,voidMiniSpanTree_Prim(MGraphG,VertexTypeu)/*从顶点u出发，按普里姆算法构造连通网G的最小生成树，并输出生成树的每条边，这里假设用邻接矩阵存储图*/k=LocateVertex(G,u);/取得u存储的下标for(j=0;jG.vexnum;j+)/初始化除定点k之外的其他点的最小代价边if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;for(i=1;iG.vexnum;i+)k=Minium(closedge);/去V-U集合中定点到U顶点集合中边权值最小的边printf(closedgek.adjvex,G.vexsk);/*输出生成树的当前最小边*/closedgek.lowcost=0;/*将顶点k纳入U集合*/for(j=0;j6,(3,4)-6,(2,6)-11,(4,6)-14,(1,2)-16,(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33。顶点集合状态：1，2，3，4，5，6。最小生成树的边的集合：。,（2)从待选边中选一条权值最小的边为:(2,3)-5。待选的边变为：(2,4)-6,(3,4)-6,(2,6)-11,(4,6)-14,(1,2)-16,(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33。顶点集合状态变为：1，2，3，4，5，6。最小生成树的边的集合：(2,3)。,（3）从待选边中选一条权值最小的边为:(2,4)-6。待选的边变为：(3,4)-6,(2,6)-11,(4,6)-14,(1,2)-16,(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33。顶点集合状态变为：1，2，3，4，5，6。最小生成树的边的集合：(2,3),(2,4)。,（4）从待选边中选一条权值最小的边为:(3,4)-6，由于3、4在同一个顶点集合2，3，4内，故放弃。重新从待选边中选一条权值最小的边为:(2,6)-11。待选的边变为：(4,6)-14,(1,2)-16,(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33。顶点集合状态变为：1，2，3，4，6，5。最小生成树的边的集合：(2,3)，(2,4),(2,6)。,（5）从待选边中选一条权值最小的边为:(4,6)-14，由于4、6在同一个顶点集合2，3，4，6内，故放弃。重新从待选边中选一条权值最小的边为:(1,2)-16。待选的边变为：(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-33。顶点集合状态变为：1，2，3，4，6，5。最小生成树的边的集合：(2,3)，(2,4),(2,6)，(1,2)。,（6）从待选边中选一条权值最小的边为:(4,5)-18。待选的边变为：(1,5)-19,(1,6)-21,(5,6)-33。顶点集合状态变为：1，2，3，4，6，5。最小生成树的边的集合：(2,3),(2,4),(2,6),(1,2),(4,5)。至此，所有的顶点都在同一个顶点集合1，2，3，4，6，5里，算法结束。所得最小生成树如图7.20所示，其代价为：5+6+11+16+18=56。,图7.20最小生成树,7.5有向无环图的应用,一个无环的有向图称为有向无环图，简称DAG图。检查一个有向无环图是否存在环比无向图复杂，如在无向图中若发现回边（指向已访问过的顶点的边）必存在环，而对有向图有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。因此判断时，从图上某个顶点v出发，在dfs(v)结束之前，若出现一条从顶点u到顶点v的回边，说明u是v的子孙，这时必有环。有向无环图也是描述一项工程或系统的进行过程的有效工具。一个大型工程可分为若干活动（子工程），而这些子工程之间受一定条件的约束，关心的问题是：该工程能否顺序进行，估算整个工程完成所必须的最短时间拓扑排序、关键路径。,7.5.1拓扑排序（TopologicalSort）,用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网（ActivityOnVertexNetwork），简称为AOV-网。,表72课程关系,图7.21表示课程之间优先关系的有向无环图,在有向图G=（V，E）中，V中顶点的线性序列（vi1,vi2,vi3，vin）称为拓扑序列，序列必须满足如下条件：对序列中任意两个顶点vi、vj，如果在G中有一条从vi到vj的路径，则在序列中vi必排在vj之前。例如，图7.21的一个拓扑序列为：C1,C2,C3,C4,C5,C8,C9,C7,C6。,AOV-网的特性如下：若vi为vj的先行活动，vj为vk的先行活动，则vi必为vk的先行活动，即先行关系具有可传递性。从离散数学的观点来看，若有、，则必存在。显然，在AOV-网中不能存在回路，否则回路中的活动就会互为前驱，从而无法执行。AOV-网的拓扑序列不是唯一的。例如，图7.21的另一个拓扑序列为：C1,C2,C3,C8,C4,C5,C9,C7,C6。,拓扑排序的基本思想为：（1）从有向图中选一个无前驱的顶点输出；（2）将此顶点和以它为起点的弧删除；（3）重复（1）、（2），直到不存在无前驱的顶点；（4）若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。,图7.22AOV-网,例如，对于图7.22所示的AOV-网，执行上述过程可以得到如下拓扑序列：v1，v6，v4，v3，v2，v5或v1，v3，v2，v6，v4，v5,基于邻接表的存储结构入度为零的顶点即为没有前驱的顶点，我们可以附设一个存放各顶点入度的数组indegree，于是有（1）找G中无前驱的顶点查找indegreei为零的顶点vi；（2）删除以i为起点的所有弧对链在顶点i后面的所有邻接顶点k，将对应的indegreek减1。为了避免重复检测入度为零的顶点，可以再设置一个辅助栈，若某一顶点的入度减为0，则将它入栈。每当输出某一入度为0的顶点时，便将它从栈中删除。,StatusTopologicalSort(ALGraphG)FindInDegree(G,indegree);/求得每个顶点的入度InitStack(S);/初始化一个栈for(i=0;inextarc)k=p-adjvex;/对i号顶点的每个邻接点入度减1if(!(-indegreek)Push(S,k);/若入度减为0，则入栈if(countG.vexnum)returnERROR;elsereturnOK;,7.5.2关键路径,有向图在工程计划和经营管理中有着广泛的应用。通常用有向图来表示工程计划时有两种方法：用顶点表示活动，用有向弧表示活动间的优先关系，即上节所讨论的AOV-网。用顶点表示事件，用弧表示活动，弧的权值表示活动所需要的时间。我们把用第二种方法构造的有向无环图叫做边表示活动的网（ActivityOnEdgeNetwork）,简称AOE-网。,AOE-网在工程计划和管理中很有用。在研究实际问题时，人们通常关心的是：哪些活动是影响工程进度的关键活动？至少需要多长时间能完成整个工程？在AOE网中存在唯一的、入度为零的顶点，叫做源点；存在唯一的、出度为零的顶点，叫做汇点。从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做关键路径。关键路径上的活动叫做关键活动。这些活动中的任意一项活动未能按期完成，则整个工程的完成时间就要推迟。相反，如果能够加快关键活动的进度，则整个工程可以提前完成。,图7.24AOE-网,事件vi的最早发生时间ve(i)：从源点到顶点vi的最长路径的长度，叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。求ve(i)时可从源点开始，按拓扑顺序向汇点递推：ve(0)=0；ve(i)=Maxve(k)dut()T,1in-1;其中，T为所有以i为头的弧的集合，dut()表示与弧对应的活动的持续时间。,事件vi的最晚发生时间vl(i)：在保证汇点按其最早发生时间发生这一前提下，求事件vi的最晚发生时间。在求出ve(i)的基础上，可从汇点开始，按逆拓扑顺序向源点递推，求出vl(i)：vl(n-1)=ve(n-1)；vl(i)=Minvl(k)dut()S,0in-2;其中，S为所有以i为尾的弧的集合，dut()表示与弧对应的活动的持续时间。,活动ai的最早开始时间e(i)：如果活动ai对应的弧为，则e(i)等于从源点到顶点j的最长路径的长度，即：e(i)=ve(j)活动ai的最晚开始时间l(i)：如果活动ai对应的弧为，其持续时间为dut(),则有：l(i)=vl(k)-dut()，即在保证事件vk的最晚发生时间为vl(k)的前提下，活动ai的最晚开始时间为l(i)。活动ai的松弛时间（时间余量）：ai的最晚开始时间与ai的最早开始时间之差：l(i)-e(i)。显然，松弛时间（时间余量）为0的活动为关键活动。,图7.24AOE-网,求关键路径的基本步骤如下：（1）对图中顶点进行拓扑排序，在排序过程中按拓扑序列求出每个事件的最早发生时间ve(i)；（2）按逆拓扑序列求每个事件的最晚发生时间vl(i)；（3）求出每个活动ai的最早开始时间e(i)和最晚发生时间l(i)；（4）找出e(i)=l(i)的活动ai，即为关键活动。,图7.25关键路径,例如，对图7.24所示的AOE-网计算关键路径的过程如下:计算各顶点的最早开始时间：ve(0)=0ve(1)=maxve(0)+dut()=6ve(2)=maxve(0)+dut()=4ve(3)=maxve(0)+dut()=5ve(4)=maxve(1)+dut(),ve(2)+dut()=7ve(5)=maxve(3)+dut()=7ve(6)=maxve(4)=dut()=16ve(7)=maxve(4)+dut()=14ve(8)=maxve(6)+dut(),ve(7)+dut()=18,(2)计算各顶点的最迟开始时间：vl(8)=ve(8)=18vl(7)=minvl(8)-dut()=14vl(6)=minvl(8)-dut()=16vl(5)=minvl(7)-dut()=10vl(4)=minvl(6)-dut(),vl(7)-dut()=7vl(3)=minvl(5)-dut()=8vl(2)=minvl(4)-dut()=6vl(1)=minvl(4)-dut()=6vl(0)=minvl(1)-dut(),vl(2)-dut(),vl(3)-dut()=0,(3)计算各活动的最早开始时间：e(a1)=ve(0)=0e(a2)=ve(0)=0e(a3)=ve(0)=0e(a4)=ve(1)=6e(a5)=ve(2)=4e(a6)=ve(3)=5e(a7)=ve(4)=7e(a8)=ve(4)=7e(a9)=ve(5)=7e(a10)=ve(6)=16e(a11)=ve(7)=14,(4)计算各活动的最迟开始时间：l(a11)=vl(8)-dut()=14l(a10)=vl(8)-dut()=16l(a9)=vl(7)-dut()=10l(a8)=vl(7)-dut()=7l(a7)=vl(6)-dut()=7l(a6)=vl(5)-dut()=8l(a5)=vl(4)-dut()=6l(a4)=vl(4)-dut()=6l(a3)=vl(3)-dut()=3l(a2)=vl(2)-dut()=2l(a1)=vl(1)-dut()=0,对图7.24所示网的计算结果如下所示。,7.6最短路径,7.6.1求某一顶点到其它各顶点的最短路径,图7.26一个带权有向图及其邻接矩阵,表73v0到其它顶点的最短路径,对于给定的有向图G=(V，E)及单个源点Vs，求Vs到G的其余各顶点的最短路径。Dijkstra提出了一种按路径长度递增次序产生最短路径的算法，即迪杰斯特拉Dijkstra算法。基本思想从图的给定源点到其它各个顶点之间客观上应存在一条最短路径，在这组最短路径中，按其长度的递增次序，依次求出到不同顶点的最短路径和路径长度。,即按长度递增的次序生成各顶点的最短路径，即先求出长度最小的一条最短路径，然后求出长度第二小的最短路径，依此类推，直到求出长度最长的最短路径。算法思想说明设给定源点为Vs，S为已求得最短路径的终点集，开始时令S=Vs。当求得第一条最短路径(Vs，Vi)后，S为Vs，Vi。根据以下结论可求下一条最短路径。设下一条最短路径终点为j，则Vj只有：源点到终点有直接的弧；Vs出发到Vj的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj。,引进一个辅助向量D，它的每一个分量Di表示当前所找到的从始点V0到每个终点Vi的最短路径长度。S表示已求得最短路径的终点集合。迪杰斯特拉算法的主要步骤如下：(1)G为用邻接矩阵表示的带权图。arcsij表示弧上的权值。令S=V0，也就是将起始点加入集合S当中，那么从V0出发到图上其余各个顶点Vi的最短路径长度的初值为：,(2)选择Vj，使得Vj为目前求得的下一条从V0出发的最短路径的终点。(3)修改从V0出发到集合V-S上任一顶点Vk的最短路径的长度。如果Dj+g.arcsjkDk则将distk修改为Dk+g.arcskj,Dj=min(Di|viV-S),(2)选择Vj，使得Vj为目前求得的下一条从V0出发的最短路径的终点。(3)修改从V0出发到集合V-S上任一顶点Vk的最短路径的长度。如果Dj+g.arcsjkDk则将distk修改为Dk+g.arcskj(4)重复(2)、(3)n-1次，即可按最短路径长度的递增顺序，逐个求出v0到图中其它每个顶点的最短路径。,Dj=min(Di|viV-S),迪杰斯克拉算法求最短路径的算法描述如下：,voidShortteatPath_DIJ(MgraphG,intv0,PathMatrix,/开始循环，每次求得V0到某个V顶点的最短路径，并加V到S集for(i=1;iG.vexnum;+i)min=INFINITY;for(w=0;wG.vexnum;+w)if(!finalw)if(Dwmin)v=w;min=Dw;/求当前最短路经finalv=TRUE;/该顶点并入S集合for(w=0;wG.vexnum;+w)/更新当前最短路径及距离if(!finalw/if/for,