第7章　图n.ppt

《第7章　图n.ppt》由会员分享，可在线阅读，更多相关《第7章　图n.ppt（110页珍藏版）》请在三一办公上搜索。

1、第七章图,7.1 抽象数据类型图的定义,7.2 图的存储表示,7.3 图的遍历,7.4 最小生成树,7.5 重（双）连通图和关节点,7.6 拓扑排序,7.7 关键路径,学习目标 掌握图的概念、存储结构、操作实现及算法复杂度；掌握图的深度、广度优先搜索遍历算法；掌握图的生成树概念，普里姆算法、克鲁斯卡算法。掌握图的拓扑排序方法,图是由一个顶点集 V 和一个弧集 R构成的数据结构。Graph=(V,R)其中，VR|v,wV 且 P(v,w)表示从 v 到 w 的一条弧，并称 v 为弧头，w 为弧尾。谓词 P(v,w)定义了弧 的意义或信息。,图的结构定义:,由于“弧”是有方向的，因此称由顶点集和弧

2、集构成的图为有向图。,AB E C D,例如:,G1=(V1,VR1),其中V1=A,B,C,D,EVR1=,若VR 必有VR,则称(v,w)为顶点v 和顶点 w 之间存在一条边。,B CA D F E,由顶点集和边集构成的图称作无向图。,例如:G2=(V2,VR2)V2=A,B,C,D,E,FVR2=,名词和术语,网、子图,完全图、稀疏图、稠密图,邻接点、度、入度、出度,路径、路径长度、简单路径、简单回路,连通图、连通分量、强连通图、强连通分量,生成树、生成森林,A,B,E,C,F,A,E,F,B,B,C,设图G=(V,VR)和图 G=(V,VR),且 VV,VRVR,则称 G 为 G 的子

3、图。,15,9,7,21,11,3,2,弧或边带权的图分别称作有向网或无向网。,假设图中有 n 个顶点，e 条边，则,含有 e=n(n-1)/2 条边的无向图称作完全图；,含有 e=n(n-1)条弧的有向图称作 有向完全图；,若边或弧的个数 enlogn，则称作稀疏图，否则称作稠密图。,假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点，,A,C,D,F,E,例如:,ID(B)=3,ID(A)=2,边(v,w)和顶点v 和w 相关联。和顶点v 关联的边的数目定义为边的度。,B,顶点的出度:以顶点v为弧尾的弧的数目；,A,B,E,C,F,对有向图来说，,顶点的入度:以顶点v为弧头

4、的弧的数目。,顶点的度(TD)=出度(OD)+入度(ID),例如:,ID(B)=2,OD(B)=1,TD(B)=3,设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1,vi,m=w中，(vi,j-1,vi,j)VR 1jm,则称从顶点u 到顶点w 之间存在一条路径。路径上边的数目称作路径长度。,A,B,E,C,F,如:长度为3的路径A,B,C,F,简单路径:序列中顶点不重复出现的路径。,简单回路:序列中第一个顶点和最后一个顶点相同的路径。,若图G中任意两个顶点之间都有路径相通，则称此图为连通图；,若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。,B,A,C,D,F,E,

5、B,A,C,D,F,E,若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。,A,B,E,C,F,A,B,E,C,F,对有向图，,否则，其各个强连通子图称作它的强连通分量。,假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。,对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。,B,A,C,D,F,E,结构的建立和销毁,插入或删除顶点,对邻接点的操作,对顶点的访问操作,遍历,插入和删除弧,基本操作,CreatGraph(&G,V,VR):/按定义(V,VR)构造图,DestroyGrap

6、h(&G):/销毁图,结构的建立和销毁,对顶点的访问操作,LocateVex(G,u);/若G中存在顶点u，则返回该顶点在/图中“位置”；否则返回其它信息。,GetVex(G,v);/返回 v 的值。,PutVex(/对 v 赋值value。,对邻接点的操作,FirstAdjVex(G,v);/返回 v 的“第一个邻接点”。若该顶点/在 G 中没有邻接点，则返回“空”。,NextAdjVex(G,v,w);/返回 v 的（相对于 w 的）“下一个邻接/点”。若 w 是 v 的最后一个邻接点，则/返回“空”。,插入或删除顶点,InsertVex(/在图G中增添新顶点v。,DeleteVex(/删

7、除G中顶点v及其相关的弧。,插入和删除弧,InsertArc(/在G中增添弧，若G是无向的，/则还增添对称弧。,DeleteArc(/在G中删除弧，若G是无向的，/则还删除对称弧。,遍 历,DFSTraverse(G,v,Visit();/从顶点v起深度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。,BFSTraverse(G,v,Visit();/从顶点v起广度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。,7.2 图的存储表示,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,Aij=,0(i,j)VR,1(i,j)VR,一、图的数组(邻接矩阵)存储表示

8、,B,A,C,D,F,E,定义:矩阵的元素为,有向图的邻接矩阵为非对称矩阵,A,B,E,C,F,网的邻接矩阵可定义为：,v1 v2 v3 v4 v5 v6,v1 v2 v3 v4 v5 v6,typedef struct ArcCell/弧的定义 VRType adj;/VRType是顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型。InfoType*info;/该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;,typedef struct/图的定义 VertexType/顶点信息 vexsMAX_VERTEX

9、_NUM;AdjMatrix arcs;/弧的信息 int vexnum,arcnum;/顶点数，弧数 GraphKind kind;/图的种类标志 MGraph;,0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3,B,A,C,D,F,E,二、图的邻接表 存储表示,1 4,2,3,0 1,2,0 1 2 3 4,A B C D E,有向图的邻接表,A,B,E,C,F,可见，在有向图的邻接表中不易找到指向该顶点的弧。,A,B,E,C,D,有向图的逆邻接表,A B C D E,3,0,3,4,2,0,01234,在有向图的邻接表中，对每个顶点，链接的是指

10、向该顶点的弧。,typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode*nextarc;/指向下一条弧的指针 InfoType*info;/该弧相关信息的指针 ArcNode;,adjvex nextarc info,弧的结点结构,typedef struct VNode VertexType data;/顶点信息 ArcNode*firstarc;/指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;,data firstarc,顶点的结点结构,typedef struct AdjList ve

11、rtices;int vexnum,arcnum;int kind;/图的种类标志 ALGraph;,图的结构定义,邻接表与邻接矩阵有什么异同之处？,联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（en2),7.3 图的遍历,从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每

12、个顶点仅被访问一次的过程。,深度优先搜索,广度优先搜索,遍历应用举例,从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。,一、深度优先搜索遍历图,连通图的深度优先搜索遍历,例：,V1,顶点访问次序：,V2,V4,V8,V5,V3,V6,V7,V1,V2,V5,V8,V4,V3,V6,V7,V1,V2,V4,V8,V5,V3,V7,V6,V1,V2,V5,V8,V4,V3,V7,V6,V1,V3,V6,V7,V2,V4,V8,V5,连通图的深度优先遍历类似于树的先根遍历,V,w1,SG1,SG2,SG3

13、,W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,访问顶点 V：for(W1、W2、W3)若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。,w2,w3,w2,从上页的图解可见:,1.从深度优先搜索遍历连通图的过程类似于树的先根遍历；,解决的办法是：为每个顶点设立一个“访问标志 visitedw”。,2.如何判别V的邻接点是否被访问？,void DFS(Graph G,int v)/从顶点v出发，深度优先搜索遍历连通图 G visitedv=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;

14、w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w/递归调用DFS/DFS,首先将图中每个顶点的访问标志设为 FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。,非连通图的深度优先搜索遍历,void DFSTraverse(Graph G,Status(*Visit)(int v)/对图 G 作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;vG.vexnum;+v)

15、if(!visitedv)DFS(G,v);/对尚未访问的顶点调用DFS,a,b,c,h,d,e,k,f,g,F F F F F F F F F,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b,g,a,c,h,k,f,e,d,b,g,访问标志:,访问次序:,例如:,0 1 2 3 4 5 6 7 8,a b c d e f g h k,从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。,若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作

16、起始点，重复上述过程，直至图中所有顶点都被访问到为止。,二、广度优先搜索遍历图,V,w1,w8,w3,w7,w6,w2,w5,w4,对连通图，从起始点V到其余各顶点必定存在路径。,其中，V-w1,V-w2,V-w8 的路径长度为1；,V-w7,V-w3,V-w5 的路径长度为2；,V-w6,V-w4 的路径长度为3。,w1,V,w2,w7,w6,w3,w8,w5,w4,1,3,4,0,V1,V2,V3,V4,V5,V6,实现：,0 1 2 3 4 5 6 7,V1 V2 V3 V4 V5 V6 V7 V8,0 1 2 3 4 5 6 7,2,V7,5,V8,6,7,1,1,1,1,1,1,1,

17、1,void BFSTraverse(Graph G,Status(*Visit)(int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化访问标志 InitQueue(Q);/置空的辅助队列Q for(v=0;vG.vexnum;+v)if(!visitedv)/v 尚未访问/BFSTraverse,visitedv=TRUE;Visit(v);/访问vEnQueue(Q,v);/v入队列while(!QueueEmpty(Q)DeQueue(Q,u);/队头元素出队并置为u for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex

18、(G,u,w)if(!visitedw)visitedw=TRUE;Visit(w);EnQueue(Q,w);/访问的顶点w入队列/if/while,三、遍历应用举例,1.求一条从顶点 i 到顶点 s 的 简单路径,2.求两个顶点之间的一条路径 长度最短的路径,1.求一条从顶点 i 到顶点 s 的简单路径,a,b,c,h,d,e,k,f,g,求从顶点 b 到顶点 k 的一条简单路径。,从顶点 b 出发进行深度优先搜索遍历。,例如:,假设找到的第一个邻接点是a，则得到的结点访问序列为:b a d h c e k f g。,假设找到的第一个邻接点是c，则得到的结点访问序列为:b c h d a

19、e k f g，,1.从顶点 i 到顶点 s,若存在路径，则从顶点 i 出发进行深度优先搜索，必能搜索到顶点 s。,2.遍历过程中搜索到的顶点不一定是路径上的顶点。,结论:,3.由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。,void DFSearch(int v,int s,char*PATH)/从第v个顶点出发递归地深度优先遍历图G，/求得一条从v到s的简单路径，并记录在PATH中 visitedv=TRUE;/访问第 v 个顶点 Append(PATH,getVertex(v);/第v个顶点加入路径 for(w=FirstAdjVex(v);w!=0/从路径上删除顶点 v,2

20、.求两个顶点之间的一条路径 长度最短的路径,若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。如何求得这条路径?,a,b,c,h,d,e,k,f,g,因此，求路径长度最短的路径可以基于广度优先搜索遍历进行，但需要修改链队列的结点结构及其入队列和出队列的算法。,深度优先搜索访问顶点的次序取决于图的存储结构，而广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。,例如:求下图中顶点 3 至顶点 5 的一条最短路径。,链队列的状态如下所示:,3 1 2 4 7 5,Q.front Q.rear,3,2,1,4,7,5,6,8,9,采用双向链队列如下所示:,3 1 2 4 7 5,Q.f

21、ront Q.rear,3,2,1,4,7,5,6,8,9,1)将链队列的结点改为“双链”结点。即结点中包含next 和priou两个指针；,2)修改入队列的操作。插入新的队尾结点时，令其priou域的指针指向刚刚出队列的结点，即当前的队头指针所指结点；,3)修改出队列的操作。出队列时，仅移动队头指针，而不将队头结点从链表中删除。,typedef DuLinkList QueuePtr;void InitQueue(LinkQueue e=Q.front-data,7.4(连通网的)最小生成树,假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费

22、的前提下建立这个通讯网？,问题：,19,17,最小生成树：给定一个无向网络，在该网的所有生成 树中，使得各边权数之和最小的那棵生成树称为该网的最 小生成树，也叫最小代价生成树。,构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。,算法二：（克鲁斯卡尔算法）,该问题等价于：,算法一：（普里姆算法）,取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-

23、1 个顶点为止。,普里姆算法的基本思想:,在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,一般情况下所添加的顶点应满足下列条件:,a,b,c,d,e,g,f,例如:,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,所得生成树权值和,=14+8+3+5+16+21=67,设置一个辅助数组，对当前VU集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：,struct VertexType adjve

24、x;/U集中的顶点序号 VRType lowcost;/边的权值 closedgeMAX_VERTEX_NUM;,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,7,a,a,a,19,14,18,14,例如:,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,a b c d e f g,设置一个辅助数组，对当前VU集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：,struct VertexType adjvex;/U集中的顶点序号 VRType lowcost;/边的权值 closedgeMAX_VERTE

25、X_NUM;,void MiniSpanTree_P(MGraph G,VertexType u)/用普里姆算法从顶点u出发构造网G的最小生成树 k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始，Uu for(i=0;iG.vexnum;+i),继续向生成树上添加顶点;,k=minimum(closedge);/求出加入生成树的下一个顶点(k)printf(closedgek.adjvex,G.vexsk);/输出生成树上一条边 clos

26、edgek.lowcost=0;/第k顶点并入U集 for(j=0;jG.vexnum;+j)/修改其它顶点的最小边 if(G.arcskj.adj closedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;,具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。,考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,克鲁斯卡尔算法的基本思想：,a,b,c,d,e,g,f,19,5,14,18,27,

27、16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,例如:,7,12,18,19,算法描述:,构造非连通图 ST=(V,);k=i=0;/k 计选中的边数 while(kn-1)+i;检查边集 E 中第 i 条权值最小的边(u,v);若(u,v)加入ST后不使ST中产生回路，则 输出边(u,v);且 k+;,Flash演示,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n2),O(eloge),稠密图,稀疏图,算法名,适应范围,比较两种算法,7.5 重（双）连通图 和关节点,若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为

28、重（双）连通图。,问题：,若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。,没有关节点的连通图为双连通图。,如何判别给定的连通图是否是双连通图？,a,h,g,c,b,f,d,e,a,b,c,d,e,f,g,h,1,2,3,4,5,6,7,8,3,3,1,1,1,1,1,1,例如:下列连通图中，,顶点 a 和顶点 c 是关节点,深度优先生成树,关节点有何特征？,假设从某个顶点V0出发对连通图进行深度优先搜索遍历，则可得到一棵深度优先生成树，树上包含图的所有顶点。,需借助图的深度优先生成树来分析。,若生成树的根结点，有两个或两个以上的分支

29、，则此顶点(生成树的根)必为关节点；,对生成树上的任意一个“顶点”，若其某棵子树的根或子树中的其它“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。,对上述两个判定准则在算法中如何实现？,1)设V0为深度优先遍历的出发点 p=G.vertices0.firstarc;v=p-adjvex;DFSArticul(G,v);/从第v顶点出发深度优先搜索 if(count G.vexnum)/生成树的根有至少两棵子树 printf(0,G.vertices0.data);/根是关节点,2)定义函数:low(v)=Minvisitedv,loww,visitedk 其中:顶点w 是生成树上顶点v

30、 的孩子；顶点k 是生成树上和顶点v由回边 相联接的祖先；visited记录深度优先遍历时的访问次序 若对顶点v，在生成树上存在一个子树根w，且 loww visitedv 则顶点v为关节点。,对深度优先遍历算法作如下修改：,1visitedv的值改为遍历过程中顶点的访问次序count值；,2遍历过程中求得 lowv=Minvisitedv,loww,visitedk,3从子树遍历返回时，判别lowwvisitedv?,for(p=G.verticesv0.firstarc;p;p=p-nextarc),void DFSArticul(ALGraph G,int v0)/从第v0个顶点出发深度

31、优先遍历图 G,/查找并输出关节点/DFSArticul,min=visitedv0=+count;/v0是第count个访问的顶点,并设lowv0的初值为min,/检查v0的每个邻接点,lowv0=min;,w=p-adjvex;/w为v0的邻接顶点 if(visitedw=0)/w未曾被访问 DFSArticul(G,w);/返回前求得loww else/w是回边上的顶点,if(loww min)min=loww;,if(loww=visitedv0)printf(v0,G.verticesv0.data);/输出关节点,if(visitedw min)min=visitedw;,7.6

32、拓扑排序,问题:,假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。,除最简单的情况之外，几乎所有的工程都可分为若干个称作“活动”的子工程，并且这些子工程之间通常受着一 定条件的约束，例如：其中某些子工程必须在另一些子工程完成之后才能开始。,在工程计划和管理方面的应用,AOV 网：,用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧 表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV(Activity On Vertex network)网。,AOV网邻接表表示,012345,对整个工程和系统，人们关心的是两方面的问题：一是工

33、程能否顺利进行；二是完成整个工程所必须的最短时间。,对应到有向图即为进行拓扑排序和求关键路径。,检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。,何谓“拓扑排序”？,对有向图进行如下操作：,按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。,例如：对于下列有向图,B,D,A,C,可求得拓扑有序序列：A B C D 或 A C B D,由此所得顶点的线性序列称之为拓扑有序序列,B,D,A,C,反之，对于下列有向图,不能求得它的拓扑有序序列。,因为图中存在一个回路 B,C,D,如何进行拓扑排序？,一、从有向图中选取一

34、个没有前驱 的顶点，并输出之；,重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。,二、从有向图中删去此顶点以及所 有以它为尾的弧；,a,b,c,g,h,d,f,e,a,b,h,c,d,g,f,e,在算法中需要用定量的描述替代定性的概念,没有前驱的顶点 入度为零的顶点,删除顶点及以它为尾的弧 弧头顶点的入度减1,取入度为零的顶点v;while(v0)printf(v);+m;w=FirstAdj(v);while(w0)inDegreew-;w=nextAdj(v,w);取下一个入度为零的顶点v;if mn printf(“图中有回路”);,算法描述,为避免每次都要搜索入度为零的顶点

35、，在算法中设置一个“栈”，以保存“入度为零”的顶点。,CountInDegree(G,indegree);/对各顶点求入度InitStack(S);for(i=0;iG.vexnum;+i)if(!indegreei)Push(S,i);/入度为零的顶点入栈,count=0;/对输出顶点计数while(!EmptyStack(S)Pop(S,v);+count;printf(v);for(w=FirstAdj(v);w;w=NextAdj(G,v,w)-indegree(w);/弧头顶点的入度减一 if(!indegreew)Push(S,w);/新产生的入度为零的顶点入栈 if(countG

36、.vexnum)printf(“图中有回路”),7.7 关键路径,问题:,假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。,a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,例如:,“关键活动”指的是：该弧上的权值增加 将使有向图上的最长路径的长度增加。,整个工程完成的时间为：从有向图的源点到汇点的最长路径。,源点,汇点,6,1,7,4,如何求关键活动？,“事件(顶点)”的 最早发生时间 ve(j)ve(j)=从源点到顶点j的最长路径长度；,“事件(顶点)”的 最迟发生

37、时间 vl(k)vl(k)=从顶点k到汇点的最短路径长度。,假设第 i 条弧为 则 对第 i 项活动言“活动(弧)”的 最早开始时间 ee(i)ee(i)=ve(j)；“活动(弧)”的 最迟开始时间 el(i)el(i)=vl(k)dut()；,事件发生时间的计算公式：ve(源点)=0；ve(k)=Maxve(j)+dut()vl(汇点)=ve(汇点)；vl(j)=Minvl(k)dut(),a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,0,0,0,0,0,0,0,0,0,6,4,5,7,11,5,7,15,14,18,18,18,18,18,18,18,18

38、,18,18,16,14,8,6,6,10,8,0,7,拓扑有序序列:a-d-f-c-b-e-h-g-k,0,6,4,5,7,7,15,14,18,18,14,16,10,7,8,6,6,0,0,0,0,6,4,5,7,7,7,15,14,14,16,0,2,3,6,6,8,8,7,10,算法的实现要点:,显然，求ve的顺序应该是按拓扑有序的次序；,而 求vl的顺序应该是按拓扑逆序的次序；,因为 拓扑逆序序列即为拓扑有序序列的 逆序列，,因此 应该在拓扑排序的过程中，另设一个“栈”记下拓扑有序序列。,1.熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。2.熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。,3.应用图的遍历算法求解各种简单路径问题。4.理解教科书中讨论的各种图的算法。,2.有向图的邻接表存储如下：（1）画出其邻接矩阵存储；（2）.写出顶点a到顶点i的所有简单路径。【东北大学 1997 一、5(5分)】,3设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。【北京轻工业学院 1998 八（6分）】,