数据结构(严蔚敏)精第7章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,.页,*,第七章,图,12/17/2025,.页,【课前思考】,1.同学们有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的五叉路口交通管理示意图相类似的图？,同学们一定可以画出如下所示类似的图形。,2.如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？,同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC),12/17/2025,.,【学习目标】,1领会图的类型定义。2熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。3熟练掌握图的两种遍历算法。4理解各种图的应用问题的算法。,12/17/2025,.,【重点和难点】,图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。,【知识点】,图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径。,12/17/2025,.,【学习指南】,离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效果。,本章必须完成的算法设计题为,:,7.7,7.9,7.10,7.12,7.14,7.15,7.22,12/17/2025,.,7.1 图的定义与术语,7.2 图的存储表示,7.3 图的遍历,7.4 最小生成树,7.5 重（双）连通图和关节点,7.6 两点之间的最短路径问题,7.7 拓扑排序,7.8 关键路径,12/17/2025,.,图,是由一个,顶点集,V,和一个,弧集,R,构成的数据结构。,Graph=(V,VR),其中，VR|v,wV 且 P(v,w),表示从 v 到 w 的一条弧，并称 v 为,弧头,，w 为,弧尾,。,谓词 P(v,w)定义了弧 的意义或信息。,图的结构定义:,7.1 图的定义与术语,12/17/2025,.,由于“弧”是有方向的，因此称由顶点集和弧集构成的图为,有向图,。,A,B E,C D,例如:,G,1,=(V,1,VR,1,),其中,V,1,=A,B,C,D,E,VR,1,=,12/17/2025,.,若,VR,必有,VR,则称,(v,w),为顶点,v,和顶点,w,之间存在一条,边,。,B C,A D,F E,由顶点集和边集构成的图称作,无向图,。,例如:,G,2,=(V,2,VR,2,),V,2,=A,B,C,D,E,F,VR,2,=(,A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F),12/17/2025,.,名词和术语,网、子图,完全图、稀疏图、稠密图,邻接点、度、入度、出度,路径、路径长度、简单路径、简单回路,连通图、连通分量、,强连通图、强连通分量,生成树、生成森林,12/17/2025,.,A,B,E,C,F,A,E,F,B,B,C,设图G=(V,VR)和图 G,=(V,VR),且 VV,VRVR,则称 G 为 G 的,子图,。,15,9,7,21,11,3,2,弧或边带权的图分别称作,有向网,或,无向网,。,C,12/17/2025,.,假设图中有,n,个顶点，,e,条边，则,含有,e=n(n-1)/2,条边的无向图称作,完全图,；,含有,e=n(n-1),条弧的有向图称作,有向完全图,；,若边或弧的个数,enlogn,，则称作,稀疏图,，,否则称作,稠密图,。,12/17/2025,.,假若顶点,v,和顶点,w,之间存在一条边，,则称顶点,v,和,w,互为,邻接点,，,A,C,D,F,E,例如:,ID(B)=3,ID(A)=2,边,(v,w),和顶点,v,和,w,相,关联,。,和顶点,v,关联的,边的数目,定义为顶点,v,的,度,。,B,12/17/2025,.,顶点的,出度,:,以顶点,v,为弧尾的弧的数目；,A,B,E,C,F,对有向图来说,，,顶点的,入度,:,以顶点v为弧头的弧的数目,。,顶点的,度(,TD,)=,出度(,OD,)+入度(,ID,),例如:,ID(B)=2,OD(B)=1,TD(B)=3,12/17/2025,.,设图G=(V,VR)中的一个顶点序列,u=v,i,0,v,i,1,v,i,m,=w中,，(v,i,j-1,v,i,j,),VR,1jm,则称从顶点,u,到顶点,w,之间存在一条,路径,。,路径上边(或弧)的数目称作,路径长度,。,A,B,E,C,F,如:,长度为,3,的路径,A,B,C,F,简单路径,:序列中顶点不重复出现的路径。,简单回路,:序列中第一个顶点和最后一个顶点相同的路径而其余顶点不重复。,12/17/2025,.,若图G中任意两个顶点之间都有路径相通,，,则称此图为,连通图,；,若无向图为非连通图，则图中各个极大连通子图称作此图的,连通分量,。,B,A,C,D,F,E,B,A,C,D,F,E,12/17/2025,.,若任意两个顶点之间都存在一条有向路径，则称此有向图为,强连通图,。,A,B,E,C,F,A,B,E,C,F,对有向图，,否则，其各个强连通子图称作它的,强连通分量,。,12/17/2025,.,假设一个连通图有,n,个顶点和,e,条边，其中,n-1,条边和,n,个顶点构成一个极小连通子图，称该极小连通子图为此连通图的,生成树,。,对非连通图，则称由各个连通分量的生成树的集合为此非连通图的,生成森林,。,B,A,C,D,F,E,12/17/2025,.,结构的建立和销毁,插入或删除顶点,对邻接点的操作,对顶点的访问操作,遍历,插入和删除弧,基本操作,12/17/2025,.,CreatGraph(&G,V,VR):,/按定义(V,VR)构造图,DestroyGraph(&G):,/销毁图,结构的建立和销毁,12/17/2025,.,对顶点的访问操作,LocateVex(G,u);,/若G中存在顶点u，则返回该顶点在,/图中“,位置,”,；否则返回其它信息。,GetVex(G,v);,/返回 v 的值。,PutVex(,/对 v 赋值value。,12/17/2025,.,对邻接点的操作,FirstAdjVex(G,v);,/返回 v 的“,第一个邻接点,”。若该顶点,/在 G 中没有邻接点，则返回“空”。,NextAdjVex(G,v,w);,/,/返回 v 的（相对于 w 的）“,下一个邻接,/,点,”。若 w 是 v 的最后一个邻接点，则,/返回“空”。,12/17/2025,.,插入或删除顶点,InsertVex(,/在图G中增添新顶点v。,DeleteVex(,/删除G中顶点v及其相关的弧。,12/17/2025,.,插入和删除弧,InsertArc(,/在G中增添弧，若G是无向的，,/则还增添对称弧。,DeleteArc(,/在G中删除弧，若G是无向的，,/则还删除对称弧。,12/17/2025,.,遍 历,DFSTraverse(G,v,Visit();,/从顶点v起,深度优先,遍历图G，并对每,/个顶点调用函数Visit一次且仅一次。,BFSTraverse(G,v,Visit();,/从顶点v起,广度优先,遍历图G，并对每,/个顶点调用函数Visit一次且仅一次。,12/17/2025,.,7.2 图的存储表示,一、,图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,三、有向图的十字链表存储表示,四、无向图的邻接多重表存储表示,12/17/2025,.,A,ij,=,0 (i,j),VR,1 (i,j),VR,一、,图的数组(邻接矩阵)存储表示,B,A,C,D,F,E,定义:矩阵的元素为,12/17/2025,.,有向图的邻接矩阵为非对称矩阵,A,B,E,C,F,12/17/2025,.,typedef struct,ArcCell,/,弧的定义,VRType adj;/VRType是顶点关系类型。,/对无权图，用1或0表示相邻否；,/对带权图，则为权值类型。,InfoType *info;/该弧相关信息的指针,ArcCell,AdjMatrixMAX_VERTEX_NUM,MAX_VERTEX_NUM;,12/17/2025,.,typedef struct /,图的定义,VertexType /顶点信息,vexsMAX_VERTEX_NUM;,AdjMatrix arcs;/弧的信息,int,vexnum,arcnum;/顶点数，弧数,GraphKind kind;/图的种类标志,MGraph;,12/17/2025,.,0,A,1 4,1,B,0 4 5,2,C,3 5,3,D,2 5,4,E,0 1,5,F,1 2 3,B,A,C,D,F,E,二、图的邻接表,存储表示,12/17/2025,.,1 4,2,3,0 1,2,0 1 2 3 4,A,B,C,D,E,有向图的邻接表,A,B,E,C,D,可见，在有向图的邻接表中不易找到指向该顶点的弧。,12/17/2025,.,A,B,E,C,D,有向图的逆邻接表,A,B,C,D,E,3,0,3,4,2,0,0,1,2,3,4,在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。,12/17/2025,.,typedef struct,ArcNode,int,adjvex;/该弧所指向的顶点的位置,struct,ArcNode,*,nextarc;,/指向下一条弧的指针,InfoType,*,info;/该弧相关信息的指针,ArcNode;,adjvex nextarc info,弧的结点结构,12/17/2025,.,typedef struct,VNode,VertexType data;/顶点信息,ArcNode,*,firstarc;,/指向第一条依附该顶点的弧,VNode,AdjListMAX_VERTEX_NUM;,data firstarc,顶点的结点结构,12/17/2025,.,typedef struct,AdjList vertices;,int,vexnum,arcnum;,int,kind;/图的种类标志,ALGraph;,图的结构定义,12/17/2025,.,三、有向图的十字链表存储表示,弧的结点结构,弧尾顶点位置 弧头顶点位置 弧的相关信息,指向下一个,有相同弧尾,的结点,指向下一个,有相同弧头,的结点,typedef struct,ArcBox,/,弧,的结构表示,int,tailvex,headvex;InfoType *info;,struct ArcBox,*,hlink,*,tlink;,VexNode;,12/17/2025,.,顶点的结点结构,顶点信息数据,指向该顶点的,第一条入弧,指向该顶点的,第一条出弧,typedef struct,VexNode,/顶点的结构表示,VertexType data;,ArcBox,*,firstin,*,firstout;,VexNode;,12/17/2025,.,typedef struct,VexNode xlistMAX_VERTEX_NUM;,/顶点结点(表头向量),int,vexnum,arcnum;,/有向图的当前顶点数和弧数,OLGraph;,有向图的结构表示(十字链表),12/17/2025,.,四、无向图的邻接多重表存储表示,typedef struct,Ebox,VisitIf mark;/访问标记,int,ivex,jvex;/该边依附的两个顶点的位置,struct,EBox,*,ilink,*,jlink;/分别指向依附这两个顶点的下一条边,InfoType,*,info;/该边信息指针,EBox;,边的结构表示,12/17/2025,.,typedef struct /邻接多重表,VexBox adjmulistMAX_VERTEX_NUM;,int,vexnum,edgenum;,AMLGraph;,顶点的结构表示,typedef struct,VexBox,VertexType data;,EBox,*,firstedge;/指向第一条依附该顶点的边,VexBox;,无向图的结构表示,12/17/2025,.,7.3 图的遍历,从图中某个顶点出发游历图，访遍,图中其余顶点，并且使图中的每个顶点,仅被访问一次的过程。,深度优先搜索,广度优先搜索,遍历应用举例,12/17/2025,.,从图中某个顶点V,0,出发，访问此顶点，然后,依次从V,0,的各个未被访问的邻接点出发深度优先搜索遍历图,，,直至图中所有和V,0,有路径相通的顶点都被访问到。,一、深度优先搜索遍历图,连通图的深度优先搜索遍历,12/17/2025,.,V,w,1,SG,1,SG,2,SG,3,W,1,、W,2,和W,3,均为 V 的邻接点，SG,1,、SG,2,和 SG,3,分别为含顶点,W,1,、W,2,和W,3,的子图。,访问顶点 V：,for(W,1,、W,2,、W,3,),若,该邻接点,W未被访问,，,则,从它出发进行深度优先搜索遍历。,w,2,w,3,w,2,12/17/2025,.,从上页的图解可见:,1.从深度优先搜索遍历连通图的过程类似于树的先根遍历；,解决的办法是：为每个顶点设立一个,“访问标志 visitedw”,。,2.如何判别V的邻接点是否被访问？,12/17/2025,.,void,DFS(Graph G,int,v),/,从顶点v出发，,深度优先搜索遍历连通图 G,visitedv=,TRUE,;VisitFunc(v);,for,(w=FirstAdjVex(G,v);,w,!=,0;w=NextAdjVex(G,v,w),if,(,!,visitedw)DFS(G,w);,/对v的尚未访问的邻接顶点w,/递归调用DFS,/DFS,12/17/2025,.,首先将图中每个顶点的访问标志设为 FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。,非连通图的深度优先搜索遍历,12/17/2025,.,void,DFSTraverse(Graph G,Status,(,*,Visit)(int v),/对图 G 作深度优先遍历。,VisitFunc=Visit;,for,(v=0;vG.vexnum;,+,v),visitedv=,FALSE,;,/访问标志数组初始化,for,(v=0;vw,1,V-w,2,V-w,8,的路径长度为1；,V-w,7,V-w,3,V-w,5,的,路径长度为,2,；,V-w,6,V-w,4,的路径长度为,3,。,w,1,V,w,2,w,7,w,6,w,3,w,8,w,5,w,4,12/17/2025,.,从图中的某个顶点V,0,出发，并在访问此顶点之后,依次访问V,0,的所有,未被访问,过的邻接点,，之后,按这些顶点被访问的先后次序依次访问它们的邻接点,，直至图中所有和V,0,有路径相通的顶点都被访问到。,若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,12/17/2025,.,void,BFSTraverse(Graph G,Status,(,*,Visit),(int,v),for,(v=0;vG.vexnum;,+,v),visitedv=,FALSE,;,/,初始化访问标志,InitQueue(Q);,/置空的辅助队列Q,for,(v=0;vnext=Q.rear-next=NULL,void,EnQueue(LinkQueue,&,Q,QelemType e),p=(QueuePtr),malloc,(,sizeof,(QNode);,p-data=e;p-next=,NULL,;,p-prior=Q.front,Q.rear-next=p;Q.rear=p;,void,DeQueue(LinkQueue,&,Q,QelemType,&,e),Q.front=Q.front-next;e=Q.front-data,12/17/2025,.,7.4 (连通网的)最小生成树,假设要在,n,个城市之间建立通讯联络网，则连通,n,个城市只需要修建,n-1,条线路，,如何在最节省经费的前提下建立,这个,通讯网,？,问题：,12/17/2025,.,构造网的一棵最小生成树，即：,在 e 条带权的边中选取 n-1 条边（不构成回路），使“,权值之和,”为最小,。,算法二：（克鲁斯卡尔算法）,该问题等价于：,算法一：（普里姆算法）,12/17/2025,.,取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。,在待添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小,。之后继续往生成树上添加顶点，直至生成树上含有 n个顶点为止。,普里姆算法的基本思想:,12/17/2025,.,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,12/17/2025,.,在生成树的构造过程中，图中 n 个顶点分属两个集合：,已落在生成树上的顶点集,U,和尚未落在生成树上的顶点集,V-U,，则应,在所有连通U中顶点和V-U中顶点的边中选取权值最小的边,。,一般情况下所添加的顶点应满足下列条件,:,12/17/2025,.,设置一个辅助数组，对当前VU集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：,struct,VertexType adjvex;,/,U集中的顶点序号,VRType lowcost;,/边的权值,closedgeMAX_VERTEX_NUM;,12/17/2025,.,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,12/17/2025,.,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),继续向生成树上添加顶点;,12/17/2025,.,k=minimum(closedge),;,/求出加入生成树的下一个顶点(k),printf,(closedgek.adjvex,G.vexsk);,/输出生成树上一条边,closedgek.lowcost=0;/第k顶点并入U集,for,(j=0;jG.vexnum;,+,j),/,修改其它顶点的最小边,if(G.arcskj.adj closedgej.lowcost),closedgej=G.vexsk,G.arcskj.adj;,12/17/2025,.,具体做法:,先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。,考虑问题的出发点:,为使生成树上,边的权值之和达到最小,，则应使生成树中每一条边的权值尽可能地小。,克鲁斯卡尔算法的基本思想：,12/17/2025,.,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,例如:,7,12,18,19,12/17/2025,.,算法描述:,构造非连通图 ST=(V,);,k=i=0;/k 计选中的边数,while,(kadjvex;,DFSArticul(G,v);,/从第v顶点出发深度优先搜索,if,(count nextarc),void DFSArticul(ALGraph G,int v0),/,从第,v0,个顶点出发深度优先遍历图,G,/,查找并输出关节点,/,DFSArticul,min=visitedv0=,+,count;,/,v0是第count个访问的顶点,并设lowv0的初值为min,/检查v0的每个邻接点,lowv0=min;,12/17/2025,.,w=p-adjvex;/w为v0的邻接顶点,if,(visitedw,=,0),/w未曾被访问,DFSArticul(G,w);/返回前求得loww,else,/w是回边上的顶点,if,(loww=,visitedv0),printf,(v0,G.verticesv0.data);,/,输出关节点,if,(visitedw min)min=visitedw;,12/17/2025,.,7.6 两点之间的 最短路径问题,求从某个源点到其余各点的最短路径,每一对顶点之间的最短路径,12/17/2025,.,求,从源点到其余各点的最短路径,的算法的基本思想:,依,最短路径的长度,递增的次序求得各条路径,源点,v,1,其中，,从源点到顶点v的最短路径,是所有路径中长度最短者。,v,2,12/17/2025,.,在这条路径上，,必定只含一条弧,，并且这条弧的,权值最小。,下一条,路径长度次短,的,最短路径,的特点：,路径长度最短,的,最短路径,的特点：,它只可能有两种情况：或者是,直接从源点到该点,(只含一条弧)；或者是,从源点经过顶点v,1,，再到达该顶点,(由两条弧组成)。,12/17/2025,.,其余最短路径的特点：,再下一条,路径长度次短,的,最短路径,的特点:,它可能有三种情况：或者是,直接从源点到该点,(只含一条弧)；或者是,从源点经过顶点v,1,，再到达该顶点,(由两条弧组成)；或者是从源点经过顶点v,2,，再到达该顶点。,它或者是,直接从源点到该点,(只含一条弧)；或者是,从源点经过已求得最短路径的顶点，再到达该顶点,。,12/17/2025,.,求最短路径的迪杰斯特拉算法：,一般情况下，,Distk=,或者=,+,。,设置辅助数组,Dist，其中每个分量Distk 表示,当前所求得的从源点到其余各顶点 k 的最短路径。,12/17/2025,.,1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。,2）修改其它各顶点的,Dist,k,值。,假设求得最短路径的顶点为u，,若,Dist,u,+,G.arcs,u,k,Dist,k,则将,Dist,k,改为,Dist,u,+,G.arcs,u,k,。,V0和k之间存在弧,V0和k之间不存在弧,其中的最小值即为最短路径的长度,。,12/17/2025,.,求每一对顶点之间的最短路径,弗洛伊德算法的基本思想是：,从 v,i,到 v,j,的所有可能存在的路径中，选出一条长度最短的路径,。,12/17/2025,.,若存在，则存在路径v,i,v,j,/路径中不含其它顶点,若,存在，则存在路径v,i,v,1,v,j,/路径中所含顶点序号不大于1,若v,i,v,2,v,2,v,j,存在，,则存在一条路径v,i,v,2,v,j,/路径中所含顶点序号不大于2,依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。,12/17/2025,.,7.7 拓扑排序,问题:,假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。,检查有向图中是否存在回路的方法之一，是对有向图进行,拓扑排序,。,12/17/2025,.,何谓“拓扑排序”？,对有向图进行如下操作：,按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。,12/17/2025,.,例如：对于下列有向图,B,D,A,C,可求得,拓扑有序序列,：,A B C D,或,A C B D,由此所得顶点的线性序列称之为,拓扑有序序列,12/17/2025,.,B,D,A,C,反之，对于下列有向图,不能求得它的拓扑有序序列。,因为图中存在一个回路 B,C,D,12/17/2025,.,如何进行拓扑排序？,一、从有向图中选取一个,没有前驱,的顶点，并输出之；,重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止,。,二、从有向图中,删去此顶点以及所,有以它为尾的弧,；,12/17/2025,.,a,b,c,g,h,d,f,e,a,b,h,c,d,g,f,e,在算法中需要用定量的描述替代定性的概念,没有前驱的顶点,入度为零的顶点,删除顶点及以它为尾的弧,弧头顶点的入度减1,12/17/2025,.,取入度为零的顶点v;,while,(v0),printf,(v);,+,m;,w:=FirstAdj(v);,while,(w0),inDegreew,-,;,w:=nextAdj(v,w);,取下一个入度为零的顶点v;,if,mn,printf,(“图中有回路”);,算法描述,12/17/2025,.,为避免每次都要搜索入度为零的顶点，,在算法中设置一个,“栈”,，以保存“入度为零”的顶点。,CountInDegree(G,indegree);,/对各顶点求入度,InitStack(S);,for,(i=0;iG.vexnum;+i),if,(!indegreei)Push(S,i);,/,入度为零的顶点入栈,12/17/2025,.,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.vexnum),printf,(“图中有回路”),12/17/2025,.,7.8 关键路径,问题:,假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。,问：哪些子工程项是“关键工程”？,即：哪些子工程项将影响整个工程的完成期限的。,12/17/2025,.,a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,例如:,“,关键活动,”指的是,：该弧上的,权值增加,将使有向图上的,最长路径的长度增加。,整个工程完成的时间为,：从有向图的,源点,到,汇点,的最长路径。,源点,汇点,6,1,7,4,12/17/2025,.,如何求关键活动？,“事件(顶点)”的 最早发生时间,ve,(j),ve(j)=,从源点到顶点j的最长路径长度,；,“事件(顶点)”的 最迟发生时间,vl,(k),vl(k)=,从顶点k到汇点的最短路径长度,。,12/17/2025,.,假设第 i 条弧为,则 对第 i 项活动言,“活动(弧)”的 最早开始时间,ee,(i),ee(i)=ve(j)；,“活动(弧)”的 最迟开始时间,el,(i),el(i)=vl(k)dut()；,12/17/2025,.,事件发生时间的计算公式：,ve(源点)=0；,ve(k)=Maxve(j)+dut(),j为所有以k为弧头的顶点集,vl(汇点)=ve(汇点)；,vl(j)=Minvl(k)dut(),k为所有以j为弧尾的顶点集,12/17/2025,.,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,18,18,16,14,8,6,6,10,8,0,7,拓扑有序序列:,a-d-f-c-b-e-h-g-k,12/17/2025,.,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,12/17/2025,.,算法的实现要点:,显然，求,ve,的顺序应该是,按,拓扑有序,的,次序,；,而 求,vl,的顺序应该是,按,拓扑逆序,的,次序,；,因为 拓扑逆序序列即为拓扑有序序列的,逆序列,，,因此 应该在拓扑排序的过程中，,另设一个,“,栈,”,记下拓扑有序序列。,12/17/2025,.,【本章小结】,图是一种比线性表和树更复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间存在着明显的层次关系，并且每层的元素可能和下一层的多个元素（即其孩子结点）相邻，但只能和上一层的一个元素（即其双亲结点）相关。而在图形结构中，结点之间的关系可以是任意的，图中任意两个元素之间都可能相邻。和树类似，图的遍历是图的一种主要操作，可以通过遍历判别图中任意两个顶点之间是否存在路径、判别给定的图是否是连通图并可求得非连通图的各个连通分量，但对于带权图（网），其最小生成树或最短路径都取决于弧或边上的权值，则需要有特定的算法求解。,12/17/2025,.,The end.,thank you for,listening,重庆工商大学,计算机与信息工程学院,12/17/2025,.,