第七章 图.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第七章 图,图的基本概念,图,由顶点,(Vertex),集合及顶点间的关系,(,即边,Edge),集合组成的一种数据结构：,Graph,(V,E),V=x|x,某个数据对象,顶点的有穷非空集合；,E1=(x,y)|x,y,V,E1,是顶点之间关系的有穷集合，也叫做边,(Edge),集合，此时的图称为,无向图,。,或,E2=|x,y,V&Path(x,y),E2,表示从,x,到,y,的一条弧,(Arc),，且称,x,为弧尾，,y,为弧头，这样的图称为,有向图,。,有向图与无向图,在有向图中，顶点对,是有序的。,在无向图中，顶点对,(x,y),是无序的。,完全图,若有,n,个顶点的无向图有,n(n-1)/2,条边,则此图为,无向完全图,。,若有,n,个顶点的有向图有,n(n-1),条边,则此图为,有向完全图,0,0,0,0,1,1,1,1,2,2,2,2,6,5,4,3,3,无向完全图,无向图,有向图,有向完全图,邻接顶点,如果,(u,v),是,E(G),中的一条边，则称,u,与,v,互为邻接顶点。,子图,设有两个图,G,(V,E),和,G,(V,E),。若,V,V,且,E,E,则称 图,G,是 图,G,的子图。,0,1,2,3,子图,0,1,3,0,1,2,3,0,2,3,权,某些图的边具有与它相关的数,称之为权。,这种带权图叫做,网络,(Network),。,顶点的,度,(Degree),一个顶点,v,的度是与它相关联的边的条数。记作,TD(v,),。,在有向图中,顶点的度等于该顶点的,入度,与,出度,之和。,顶点,v,的入度是以,v,为终点,(,弧头,),的有向边的条数,记作,ID(v,);,顶点,v,的出度是以,v,为始点,(,弧尾,),的有向边的条数,记作,OD(v,),。,顶点的度,(TD)=,出度,(OD)+,入度,(ID),TD(B)=OD(B)+ID(B)=1+2=3,A,B,E,C,F,路径,在图,G,(V,E),中,若从顶点,vi,出发,沿一些边经过一些顶点,vp1,vp2,vpm,，到达顶点,vj,。则称顶点序列,(vi vp1 vp2.,vpm,vj,),为从顶点,vi,到顶点,vj,的路径。,它经过的边,(vi,vp1),、,(vp1,vp2),、,.,、,(,vpm,vj,),应是属于,E,的边。,路径长度,非带权图的路径长度是指此路径上,边的条数,。,带权图的路径长度是指路径上,各边的权之和,。,简单路径,若路径上各顶点,v1,v2,.,vm,均不 互相重复,则称这样的路径为简单路径。,回路,若路径上第一个顶点,v1,与最后一个顶点,vm,重合,则称这样的路径为回路或环。,简单回路,若回路上各顶点,v1,v2,.,vm,均不 互相重复,则称这样的回路为简单回路。,0,1,2,3,0,1,2,3,0,1,3,2,连通图与连通分量,在无向图中,若从顶点,v1,到顶点,v2,有路径,则称顶点,v1,与,v2,是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。,非连通图的极大连通子图叫做连通分量。,强连通图与强连通分量,在有向图中,若对于每一对顶点,vi,和,vj,都存在一条从,vi,到,vj,和从,vj,到,vi,的路径,则称此图是强连通图。,非强连通图的极大强连通子图叫做强连通分量。,B,A,C,D,F,E,A,B,E,C,F,有向图,强连通图,无向图,连通图,生成树,假设一个连通图的,n,个顶点和,n-1,条边构成一个,极小连通子图,，称该极小连通子图为此连通图的生成树。,在极小连通子图中增加一条边，则一定有环。,在极小连通子图中去掉一条边，则成为非连通图,注意：有,n,个顶点，,n-1,条边的图不一定是生成树,B,A,C,D,F,E,B,A,C,D,F,E,生成森林,对非连通图，称由各个连通分量的生成树的集合为此非连通图的生成森林,图的存储结构,1,、邻接矩阵,(,数组,),表示法,有一个记录各个顶点信息的顶点表，,还有一个表示各个顶点之间关系的邻接矩阵。,设图,A=(V,E),是一个有,n,个顶点的图,图的邻接矩阵是一个二维数组,A.Edgenn,，定义：,无向图的邻接矩阵是对称的,;,0,1,2,3,0,1,2,在有向图中,统计第,i,行,1,的个数可得顶点,i,的出度，,统计第,j,列,1,的个数可得顶点,j,的入度。,在无向图中,统计第,i,行(,或,列)1 的个数可得顶点,i,的度。,网络的邻接矩阵,1,8,6,3,2,9,5,4,2,0,3,1,用邻接矩阵表示的结构定义,const,int,NumEdges,=50;/,边条数,const,int,NumVertices,=10;/,顶点个数,typedef,char,VertexData,;/,顶点数据类型,typedef,int,EdgeData,;/,边上权值类型,typedef,struct,VertexData,vexListNumVertices,;/,顶点表,EdgeData,EdgeNumVerticesNumVertices,;,/,邻接矩阵,可视为边之间的关系,int,n,e;/,图中当前的顶点个数与边数,MTGraph,;,2,、邻接表 表示法,邻接表,:,是图的一种链式存储结构。,顶点的结点结构,data;/,顶点信息,firstarc,;/,指针,指向第一条依附该顶点的弧,弧的结点结构,adjvex,;/,该弧所指向的顶点的位置,nextarc,;/,指针,指向下一条弧,info;/,该弧相关信息,adjvex,nextarc info,data firstarc,无向图的邻接表,同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边,(,边结点,),结点中有另一顶点的下标,dest,和指针,link,。,A,B,C,D,data,adj,A,B,C,D,0,1,2,3,dest,link,dest,link,1,3,0,2,1,0,有向图的邻接表和逆邻接表,dest,link,A,B,C,A,B,C,0,1,2,dest,link,邻接表,(,出边表,),1,0,2,data,adj,A,B,C,0,1,2,dest,link,逆邻接表,(,入边表,),0,1,1,data,adj,网络,(,带权图,),的邻接表,B,A,C,D,6,9,5,2,8,data,adj,A,B,C,D0,1,2,3,dest,cost,link,1,5,3,6,2,8,3,2,1,9,(,出边表,),(,顶点表,),带权图的边结点中保存该边上的权值,cost,。,顶点,i,的边链表的表头指针,adj,在顶点表的下标为,i,的顶点记录中，该记录还保存了该顶点的其它信息。,在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。,设图中有,n,个顶点，,e,条边，则用邻接表表示无向图时，需要,n,个顶点结点，,2e,个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需,n,个顶点结点，,e,个边结点。,图的邻接表存储表示,#define MAX_VERTEX_NUM 20,typedef,struct,ArcNode,int,adjvex,;/,该弧所指向的顶点的位置,struct,ArcNode,*,nextarc,;/,指向下一条弧指针,InfoType,*info;/,该弧相关信息的指针,ArcNode,;,typedef,struct,VNode,VertexType,data;/,顶点信息,ArcNode,*,firstarc,;/,指向第一条依附该顶点的弧,VNode,AdjListMAX_VERTEX_NUM,;,typedef,struct,AdjList,vertices;,int,vexnum,arcnum,;/,图的当前顶点数和弧数,int,kind,;/,图的种类标志,ALGraph,;,邻接表表示的图的定义,typedef,char,VertexData,;,/,顶点数据类型,typedef,int,EdgeData,;,/,边上权值类型,typedef,struct,node /,边结点,int,dest,;/,目标顶点下标,EdgeData,cost;/,边上的权值,struct,node*link;,/,下一边链接指针,EdgeNode,;,typedef,struct,/,顶点结点,VertexData,data;/,顶点数据域,EdgeNode,*,firstAdj,;/,边链表头指针,VertexNode,;,typedef,struct,/,图的邻接表,VertexNode,VexList,NumVertices,;/,邻接表,int,n,e;,/,图中当前的顶点个数与边数,AdjGraph,;,邻接表的构造算法,(,无向图,),void,CreateGraph,(,AdjGraph,G),cin,G.n,G.e,;/,输入顶点个数和边数,for(,int,i=0;i,G.VexListi.data,;/,输入顶点信息,G.VexListi.firstAdj,=NULL;,for(i=0;i tail head weight;,EdgeNode,*p=new,EdgeNode,;,p-,dest,=head;p-cost=weight;,/,链入第,tail,号链表的前端,p-link=,G.VexListtail.firstAdj,;,G.VexListtail.firstAdj,=p;,p=new,EdgeNode,;,p-,dest,=tail;p-cost=weight;,/,链入第,head,号链表的前端,p-link=,G.VexListhead.firstAdj,;,G.VexListhead.firstAdj,=p;,图的遍历,从图中某一顶点出发访遍图中所有的顶点，且使每个顶点仅被访问一次，这一过程就叫做图的遍历,(Traversing Graph),。,图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。,为了避免重复访问，可设置一个标记顶点是否被访问过的辅助数组,visited 0.n-1,。,辅助数组,visited ,的初始状态为,0,在图的遍历过程中,一旦某一个顶点,i,被访问,就立即让,visited i,为,1,防止它被多次访问。,两种图的遍历方法,:,深度优先搜索,DFS(Depth First Search),广度优先搜索,BFS(Breadth First Search),深度优先搜索,DFS,深度优先搜索过程,6,7,A,C,D,E,G,B,F,I,H,A,C,D,E,G,B,FI,H,1,2,3,4,5,8,9,1,2,3,4,5,6,7,8,9,深度优先生成树,前进,回退,访问图中某一起始顶点,v,后,由,v,出发,访问它的任一邻接顶点,w1;,再从,w1,出发,访问与,w1,邻 接但还没有访问过的顶点,w2;,然后再从,w2,出发,进行类似的访问,如此进行下去,直至到达所有的邻接顶点都被访问过的顶点,u,为止。,接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。,如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问,;,如果没有,就再退回一步进行搜索。,重复上述过程,直到连通图中所有顶点都被访问过为止。,图的深度优先搜索算法,void,Graph_Traverse,(,AdjGraph,G),int,*visited=new,int,NumVertices,;,for(,int,i=0;i,G.n,;i+),visited i=0;/,访问数组,visited,初始化,for(,int,i=0;i,G.n,;i+),if(!,visitedi,),DFS(G,i,visited);/,从顶点,i,出发开始搜索,delete visited;/,释放,visited,void DFS(,AdjGraph,G,int,v,int,visited ),cout,GetValue,(G,v);/,访问顶点,v,visitedv,=1;/,顶点,v,作访问标记,int,w=,GetFirstNeighbor,(G,v);,/,取,v,的第一个邻接顶点,w,while(w!=-1)/,若邻接顶点,w,存在,if(!,visitedw,)DFS(G,w,visited);,/,若,顶点,w,未访问过,递归,访问顶点,w,w=,GetNextNeighbor,(G,v,w);,/,取顶点,v,排在,w,后的下一个邻接顶点,广度优先搜索,BFS,广度优先搜索过程,A,C,D,E,G,B,F,I,H,A,C,D,E,G,B,F,H,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,广度优先生成树,I,访问了起始顶点,v,之后,由,v,出发,依次访问,v,的各个未被访问过的邻接顶点,w1,w2,wt,然后再顺序访问,w1,w2,wt,的所有还未被访问过的邻接顶点。,再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，,如此做下去，直到图中所有顶点都被访问到为止。,广度优先搜索类似于树的层序遍历,广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况。因此,广度优先搜索不是一个递归的过程。,为了实现逐层访问,算法中使用了一个,队列,以记忆正在访问的这一层和下一层的顶点,以便于向下一层访问。,为避免重复访问,需要一个辅助数组,visitedn,，给被访问过的顶点加标记。,图的广度优先搜索算法,void,Graph_Traverse,(,AdjGraph,G),int,*visited=new,int,NumVertices,;,for(,int,i=0;i,G.n,;i+),visited i=0;/,访问数组,visited,初始化,for(,int,i=0;i,G.n,;i+),if(!,visitedi,),BFS(G,i,visited);/,从顶点,i,出发开始搜索,delete visited;/,释放,visited,void BFS(,AdjGraph,G,int,v,int,visited ),cout,GetValue,(v);,visitedv,=1;,Queue q;,InitQueue(&q,);,EnQueue,(/,进队列,while(!,QueueEmpty,(&q)/,队空搜索结束,DeQueue,(,int,w=,GetFirstNeighbor,(G,v);,while(w!=-1)/,若邻接顶点,w,存在,if(!,visitedw,)/,未访问过,cout,GetValue,(w);,visitedw,=1;,EnQueue,(,w=,GetNextNeighbor,(G,v,w);,/,重复检测,v,的所有邻接顶点,/,外层循环，判队列空否,/BFS,图的连通性问题,连通分量,当无向图为非连通图时,从图中某一顶点出发,利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点,只能访问到该顶点所在的最大连通子图,(,即,:,连通分量,),的所有顶点。,若从无向图的每一个连通分量中的一个顶点出发进行遍历,可求得无向图的所有连通分量。,求连通分量的算法,需要对图的每一个顶点进行检测：,若已被访问过，则该顶点一定是落在图中已求得的连通分量上；,若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。,对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。,A,C,D,E,I,B,F,O,G,H,J,N,M,L,K,非连通无向图的三个连通分量,A,H,K,C,D,E,I,B,F,O,G,J,N,M,L,非连通图的连通分量的极小连通子图,(,生成树,),最小生成树,使用不同的遍历图的方法，可以得到不同的生成树；,从不同的顶点出发，也可能得到不同的生成树。,按照生成树的定义，,n,个顶点的连通网络的生成树有,n,个顶点和,n-1,条边。,构造最小生成树的准则,必须使用且仅使用该网络中的,n-1,条边来联结网络中的,n,个顶点；,不能使用产生回路的边；,各边上的权值的总和达到最小。,普里姆,Prim,算法,用于构造最小生成树,基本思想：,从连通网络,N=V,E,中的某一顶点,u0,出发,选择与它关联的具有最小权值的边,(u0,v),将其顶点加入到生成树顶点集合,U,中。,以后每一步从一个顶点在,U,中,而另一个顶点不在,U,中的各条边中选择权值最小的边,(u,v),把它的顶点加入到集合,U,中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合,U,中为止。,采用邻接矩阵作为图的存储表示。,25,25,10,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,5,0,4,6,1,3,2,5,0,4,6,1,3,2,10,原图,(1)(2),5,0,4,6,1,3,2,10,(3)(4)(5)(6),5,0,4,6,1,3,2,10,22,12,5,0,4,6,1,2,10,25,14,22,16,12,3,25,22,12,在构造过程中，还设置了两个辅助数组：,lowcosti,存放生成树顶点集合,内,顶点到生成树,外,顶点,i,的各边的当前最小权值；,nearvexi,记录生成树顶点集合,内,哪个顶点距离集合,外,顶点,i,最近。,例子,5,0,4,6,1,3,2,10,25,14,24,16,18,12,28,22,若选择从顶点,0,出发，即,u0=0,，则两个辅助数组的初始状态为：,然后反复做以下工作：,在,lowcost,中选择,nearvexi,-1&,lowcosti,最小的边,用,v,标记它。则选中的权值最小的边为,(,nearvexv,v),相应的权值为,lowcostv,。,将,nearvexv,改为,-1,表示它已加入生成树顶点集合。,0 28,10 ,-,1 0 0,0 0 0 0,lowcost,nearvex,0 1 2 3 4 5 6,将边,(,nearvexv,v,lowcostv,),加入生成树的边集合。,取,lowcosti,=min,lowcosti,Edgevi,，即用生成树顶点集合,外,各顶点,i,到刚加入该集合的新顶点,v,的距离,Edgevi,与原来它们到生成树顶点集合中顶点的最短距离,lowcosti,做比较,取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。,如果生成树顶点集合外顶点,i,到刚加入该集合的新顶点v,的距离比原来它到生成树顶点集合中顶点的最短距离还要近，则修改,nearvexi,:,nearvexi,=v,。表示生成树外顶点,i,到生成树内顶点,v,当前距离最近。,0,28,10,-,1,0,0,0,0,0,0,lowcost,nearvex,0 1 2 3 4 5 6,选,v=5,选边,(0,5),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边,(0,5,10),加入生成树,12,0,4,6,1,3,2,10,25,5,顶点,v=5,加入生成树顶点集合：,0,28,25,10,-,1,0,0,0,5,-,1,0,lowcost,nearvex,0 1 2 3 4 5 6,选,v=4,选边,(5,4),0 1 2 3 4 5 6,顶点,v=4,加入生成树顶点集合：,0,28,22,25,10,24,-,1,0,0,4,-,1,-,1,4,lowcost,nearvex,选,v=3,选边,(4,3),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边,(5,4,25),加入生成树,12,5,0,4,6,1,3,2,10,25,22,顶点,v=3,加入生成树顶点集合：,0,28,1,2,22,25,10,18,-,1,0,3,-,1,-,1,-,1,3,lowcost,nearvex,0 1 2 3 4 5 6,选,v=2,选边,(3,2),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边,(4,3,22),加入生成树,12,5,0,4,6,1,3,2,10,25,22,12,lowcost,nearvex,0 1 2 3 4 5 6,顶点,v=2,加入生成树顶点集合：,0,16,12,22,25,10,18,-,1,2,-,1,-,1,-,1,-,1,3,选,v=1,选边,(2,1),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边,(3,2,12),加入生成树,12,5,0,4,1,3,2,10,25,22,16,12顶点,v=1,加入生成树顶点集合：,0,16,1,2,22,25,10,14,-,1,-,1,-,1,-,1,-,1,-,1,1,lowcost,nearvex,0 1 2 3 4 5 6,选,v=6,选边,(1,6),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边,(2,1,16),加入生成树,12,5,0,4,6,1,3,2,10,25,14,22,16,12,lowcost,nearvex,0 1 2 3 4 5 6,顶点,v=6,加入生成树顶点集合：,0,16,1,2,22,25,10,14,-,1,-,1,-,1,-,1,-,1,-,1,-,15,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边,(1,6,14),加入生成树,12,5,0,4,6,1,3,2,10,25,14,22,16,12,最后生成树中边集合里存入得各条边为：,(0,5,10),(5,4,25),(4,3,22),(3,2,12),(2,1,16),(1,6,14),注意：当各边有相同权值时，由于选择的随意性，产生的生成树可能不唯一。当各边的权值不相同时，产生的生成树是唯一的,22,5,0,4,6,1,3,2,10,25,14,16,12,Prim,算法实现,最短路径,最短路径问题：,如果从图中某一顶点,(,称为源点,),到达另一顶点,(,称为终点,),的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。,问题解法,边上权值,非负,情形的单源最短路径问题,Dijkstra,算法,边上权值为任意值的单源最短路径问题,Bellman,和,Ford,算法,任意顶点之间的最短路径,Floyd,算法,边上权值非负情形的单源最短路径问题,问题的提法：给定一个带权有向图,D,与源点,v,，求从,v,到,D,中其它顶点的最短路径。限定各边上的权值大于或等于,0,。,为求得这些最短路径,Dijkstra,提出按路径长度的递增次序,逐步产生最短路径,的算法。,首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点,v,到其它各顶点的最短路径全部求出为止。,Dijkstra,逐步求解的过程,1,0,4,3,2,10,100,30,50,20,60,10,源点 终点 最短路径 路径长度,v,0,v,1,(,v,0,v,1,)10,v,2,(,v,0,v,1,v,2,),(,v,0,v,3,v,2,),60,50,v,3,(,v,0,v,3,)30,v,4,(,v,0,v,4,),(,v,0,v,3,v,4,),(,v,0,v,3,v,2,v,4,),100,90,60,引入辅助数组,dist,。它的每一个分量,disti,表示当前找到的从源点,v0,到终点,vi,的最短路径的长度。初始状态：,若从源点,v0,到顶点,vi,有边,则,disti,为该边上的权值；,若从源点,v0,到顶点,vi,无边,则,disti,为,。,设,S,是已求得的最短路径的终点的集合，可证：,下一条最短路径必然是从,v0,出发，中间只经过,S,中的顶点便可到达的那些顶点,vx,(,vx,V,S),的路径中的一条。,每次求得一条最短路径后,其终点,vk,加入集合,S,，然后对所有的,vi,V,S,，修改其,disti,值。,Dijkstra,算法,初始化：,S v0;,distj,Edge0j,j=1,2,n-1;,/n,为图中顶点个数,求出最短路径的长度：,distk,min,disti,i,V-S;,S S,U,k;/,顶点,k,加入集合,S,修改：,disti,min,disti,distk,+,Edgeki,对每一个,i,V-S,k,S;,判断：若,S=V,则算法结束，否则转。,有向无环图及其应用,一个无环的有向图称为有向无环图,DAG(Directed,Acycline,Graph),可用于描述含有公共子式的表达式,可用于描述一项工程或系统的进行过程,对于一个工程，我们关心：,工程能否顺利完成,拓扑排序问题,估算整个工程完成所必须的最短时间,关键路径问题,拓扑排序,计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。,例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有先后关系，有的课程可以并行地学习。,C,1,高等数学,C,2,程序设计基础,C,3,离散数学,C,1,C,2,C,4,数据结构,C,3,C,2,C,5,高级语言程序设计,C,2,C,6,编译方法,C,5,C,4,C,7,操作系统,C,4,C,9,C,8,普通物理,C,1,C,9,计算机原理,C,8,课程代号 课程名称 先修课程,学生课程学习工程图,C,8,C,3,C,5,C,4,C,9,C,6,C,7,C,1,C,2,可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边,表示活动,Vi,必须先于活动,Vj,进行。这种有向图叫做,顶点表示活动,的,AOV,网络,(Activity On Vertices),。,在,AOV,网络中不能出现有向回路,即有向环。如果出现了有向环，则意味着某项活动应以自己作为先决条件。,因此，对给定的,AOV,网络，必须先判断它是否存在有向环。,检测有向环的一种方法是对,AOV,网络构造它的拓扑有序序列。,即将各个顶点,(,代表各个活动,),排列成一个线性有序的序列，使得,AOV,网络中所有应存在的前驱和后继关系都能得到满足。,这种构造,AOV,网络全部顶点的拓扑有序序列的运算就叫做,拓扑排序,。,如果通过拓扑排序能将,AOV,网络的所有顶点都排入一个拓扑有序的序列中,则该网络中必定不会出现有向环。,如果,AOV,网络中存在有向环，此,AOV,网络所代表的工程是不可行的。,例如,对学生选课工程图进行拓扑排序,得到的拓扑有序序列为,C1,C2,C3,C4,C5,C6,C8,C9,C7,或,C1,C8,C9,C2,C5,C3,C4,C7,C6,C,8,C,3,C,5,C,4,C,9,C,6,C,7,C,1,C,2,拓扑排序的方法,输入,AOV,网络。令,n,为顶点个数。,在,AOV,网络中选一个没有直接前驱的顶点,并输出之,;,从图中删去该顶点,同时删去所有它发出的有向边,;,重复以上、步,直到,全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或者：,图中还有未输出的顶点,但已跳出处理循环。说明图中还剩下一些顶点,它们都有直接前驱。这时网络中必存在有向环。,C0,C1,C2,C3,C4,C5,拓扑排序的过程,(a),有向无环图,C2,C5,C1,C0,C3,(b),输出顶点,C4,C1,C2,C5,C3,(c),输出顶点,C0,C4,C0,C2,C5,C1,C3,(d),输出顶点,C3,C1,C2,C5,(e),输出顶点,C2,C5,C1,(f),输出顶点,C1,C5,(g),输出顶点,C5,(h),拓扑排序完成,最后得到的拓扑有序序列为,C4,C0,C3,C2,C1,C5,。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如,C4,和,C2,，也排出了先后次序关系。,AOV,网络及其邻接表表示,C0,C1,C2,C3,C4,C5,C0,C1,C2,C3,C4,C5,0,1,2,3,4,5,countID,data,adj,1,3,0,1,0,3,1,dest,link,3 0,5,1,5 0,0,1,5 0,在邻接表中增设一个数组,countID,，记录各顶点,入度,。,入度为零的顶点即无前驱顶点。,在输入数据前,顶点表,VexList,和入度数组,countID,全部初始化。,在输入数据时,每输入一条边,就需要建立一个边结点,并将它链入相应边链表中,统计入度信息。,在算法中,使用一个存放入度为零的顶点的链式栈,供选择和输出无前驱的顶点。,拓扑排序算法,:,1,、扫描顶点表，将入度为,0,的顶点入栈；,2,、,while (,栈非空,),将栈顶顶点,v,弹出并输出之；,检查,v,的出边，将每条出边,终点,u,的入度减,1,若,u,的入度变为,0,，则把,u,推入栈；,3,、若输出的顶点数小于,n,，则输出“有回路”；否则拓扑排序正常结束。,关键路径,如果在无有向环的带权有向图中,用有向边表示一个工程中的,活动,用边上权值表示活动持续时间,用顶点表示,事件,则这样的有向图叫做用边表示活动的网络,简称,AOE(Activity On Edges),网络。,a,9,=6,1,3,2,4,a,1,=8,a,2,=12,5,6,7,8,a,10,=12,a,8,=18,a,5,=28,a,6,=8,a,7,=6,a,3,=14,a,4,=10,AOE,网络在某些工程估算方面非常有用。例如，可以使人们了解：,完成整个工程至少需要多少时间,(,假设网络中没有环,)?,为缩短完成工程所需时间,应加快哪些活动,?,从源点到各个顶点,以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。,完成不同路径的活动所需的时间虽然不同,但只有各条路径上所有活动都完成了,整个工程才算完成。,因此,完成整个工程所需的时间取决于从源点到汇点的,最长路径,长度,即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做,关键路径,(Critical Path),。,要找出关键路径，必须找出,关键活动,：即不按期完成就会影响整个工程完成的活动。,关键路径上的所有活动都是关键活动。因此,只要找到了关键活动,就可以找到关键路径。,定义几个与计算关键活动有关的量：,事件,Vi,的最早可能开始时间,Ve,i,是从源点,V0,到顶点,Vi,的最长路径长度。,事件,Vi,的最迟允许开始时间,Vl,i,是在保证汇点,Vn-1,在,Ve,n-1,时刻完成的前提下，事件,Vi,的允许的最迟开始时间。,活动,ak,的最早可能开始时间,e,k,设活动,a,k,在边,上,则,e,k,是从源点,V0,到顶点,Vi,的最长路径长度。因此,e,k,=,Ve,i,。,活动,a,k,的最迟允许开始时间,l,k,l,k,是在不会引起时间延误的前提下,该活动允许的最迟开始时间。,l,k,=,Vl,j,-,dur,(),其中,dur,(),是完成,a,k,所需的时间。,时间余量,l,k,-,e,k,表示活动,a,k,的最早可能开始时间和最迟允许开始时间的时间余量。,l,k,=,e,k,表示活动,a,k,是没有时间余量的,关键活动,。,为找出关键活动,需要求各个活动的,e,k,与,l,k,，以判别是否,l,k,=,e,k,。,为求得,e,k,与,l,k,需要先求得从源点,V0,到各个顶点,Vi,的,Ve,i,和,Vl,i,。,求,Vei,的递推公式,从,Ve0=0,开始，,向前,递推,S2,i=1,2,n-1,S2,是所有指向,Vi,的有向边,的集合。,从,Vln-1=Ven-1,开始，,反向,递推,S1,i=n-2,n-3,0,S1,是所有源自,Vi,的有向边,的集合。,这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。,设活动,a,k,(k,=1,2,e),在带权有向边,上,其持续时间用,dur,(),表示,则有,ek,=,Vei,；,l,k,=,Vl,j,-,dur,(),；,k=1,2e,这样就得到计算关键路径的算法。,为了简化算法,假定在求关键路径之前已经对各顶点实现了拓扑排序,并按拓扑有序的顺序对各顶点重新进行了编号。,v5,v1,v2,v3,v4,v6,v7,v8,v9,4,6,5,1,1,2,9,7,4,4,2,6,4,0,5,7,7,16,14,18,18,14,10,8,6,6,16,7,0,事件最早开始时间,Ve,事件,最晚开始时间,Vl,v5,v1,v2,v3,v4,v6,v7,v8,v9,4,6,5,1,1,2,9,7,4,4,2,6,4,0,5,7,7,16,14,18,18,14,10,8,6,6,16,7,0,活动,1-2,1-3,1-4,2-5,3-5,4-6,5-7,5-8,6-8,7-9,8-9,e,0,0,0,6,4,5,7,7,7,16,14,l,0,2,3,6,6,8,7,7,10,16,14,l-e,0,2,3,0,2,3,0,0,3,0,0,v5,v1,v2,v7,v8,v9,6,1,9,7,4,2,6,0,7,16,14,18,18,14,6,16,7,0,得到的关键路径,并不是加快任何一个关键活动都可以缩短整个工程的工期。只有加快那些,包括在所有关键路径上的关键活动,才能达到这个目的。,关键活动的速度提高是有限度的。,提高到一定程度，不再是关键活动了,作业,P244,1,2,3,4,13,14(1),15,