数据结构 第7章(图).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,华电,计算机系,North China Electric Power University,第七章 图,基本术语,图的存储结构,图的遍历,最小生成树,最短路径问题,AOV,网与拓扑排序,AOE,网与关键路径,基本术语,图是由,顶点的非空有穷集合,与,顶点之间关系,(,边或弧,),的集合,构成的结构,通常表示为,G=(V,E),其中,V,为顶点集合,E,为关系,(,边或弧,),的集合,.,一,.,图的定义,(,b,),.,这条边依附于顶点,v,i,和,v,j,。,(v,i,v,j,),v,i,v,j,v,j,v,i,v,j,v,i,v,j,v,i,v,j,v,i,关于一条边或弧的表示方法,:,(,a,),.,顶点,v,i,与,v,j,是,这条边的两个邻接点。,(,1,),.,用图形,:,(2).,用符号,:,(,3,),.,用语言,:,v,1,v,2,v,3,v,4,其中,V,1,=v,1,v,2,v,3,v,4,E,1,=(v,1,v,2,),(v,1,v,3,),(v,1,v,4,),(v,2,v,3,),(v,2,v,4,),(v,3,v,4,),G,1,=(V,1,E,1,),v,1,v,2,v,3,v,4,其中,V,2,=v,1,v,2,v,3,v,4,E,2,=,G,2,=(V,2,E,2,),无向图：,有向图：,与边有关的数据称为,权,边上带权的图称为,网络,。,二,.,图的分类,对于,（,v,i,v,j,),E,必有,（,v,j,v,i,),E,，,并且偶对中顶点的前后顺序无关。,若,E,是,顶点的有序偶对。,网,(,络,),：,v,1,v,2,v,3,v,4,v,1,v,2,v,3,v,4,v,1,v,2,v,3,v,4,10,4,17,8,1,.,顶点的度,对于有向图而言,有,:,顶点的,出度,:,以顶点,v,i,为出发点的边的数目,记为,OD(v,i,).,顶点的,入度,:,以顶点,v,i,为终止点的边的数目,记为,ID(v,i,).,TD(v,i,)=OD(v,i,)+ID(v,i,),三,.,名词术语,依附于顶点,v,i,的边的数目,记为,TD(v,i,).,v,1,v,3,v,4,v,1,v,2,v,3,v,4,v,2,边的数目达到最大的图称为,完全图,.,边的数目达到或接近最大的图称为,稠密图,否则,称为,稀疏图,.,具有,n,个顶点的有向图最多有,n(n-1),条边,.,具有,n,个顶点的无向图最多有,n(n-1)/2,条边,.,对于具有,n,个顶点,e,条边的图,有,2e,=,TD(v,i,),n,i=1,结论,1,结论,2,结论,3,2,.,路径,D,C,E,B,A,P(A,E):,A,B,E,A,C,D,E,出发点与终止点相同的路径称为,回路或环,；顶点序列中顶点不重复出现的路径称为,简单路径,。,不带权的图的路径长度,是指路径上所经过的边的数目，,带权的图的路径长度,是指路径上经过的边上的权值之和。,顶点,v,x,到,v,y,之间有路径,P(v,x,v,y,),的,充分必要条件为,:,存在顶点序列,v,x,v,i1,v,i2,v,im,v,y,并且序列中相邻两个顶点构造的顶点偶对分别为图中的一条边。,3,.,子图,v,1,v,2,v,3,v,4,对于图,G=(V,E),与,G,=(V,E,),若有,V,V,E,E,则称,G,为,G,的,一个子图,.,v,1,v,2,v,3,v,4,v,1,v,2,4,.,图的连通,无向图中顶点,v,i,到,v,j,有,路径,则称,顶点,v,i,与,v,j,是,连通的,。,若无向图中任意两个顶点都连通,则称该,无向图是连,通的。,若有向图中顶点,v,i,到,v,j,有,路径,并且顶点,v,j,到,v,i,也有路,径,则称顶点,v,i,与,v,j,是,连通的。,若有向图中任意两个顶点都连通,则称该有向图是,强,连通的。,(1),.,无向图的连通,(2),.,有向图的连通,(3),.,连通分量 强连通分量,5,.,生成树,包含具有,n,个顶点的连通图,G,的全部,n,个顶点,仅包,含其,n-1,条边的连通子图称为,G,的一个生成树。,v,1,v,3,v,4,v,2,v,1,v,3,v,4,v,2,v,1,v,3,v,4,v,2,v,1,v,3,v,4,v,2,v,1,v,3,v,4,v,2,对于一个图,需要存储的信息应该包括,:,(,1,).,所有顶点的数据信息；,(,2,).,顶点之间关系,(,边或弧,),的信息,;,(,3,).,权的信息。,图的存储结构,一,.,邻接矩阵存储方法,核心思想,:,采用两个数组存储一个图,.,1,.,定义一个一维数组,VERTEXn,存放图中所有顶点,的数据信息,.,2,.,定义一个二维数组,An,n,存放图中所有顶点之,间关系的信息,(,该数组被称为邻接矩阵,),有,1,当顶点,v,i,到顶点,v,j,有边时,Ai,j=,0,当顶点,v,i,到顶点,v,j,无边时,对于带权的图,有,w,ij,当顶点,v,i,到顶点,v,j,有边,且边的权为,w,ij,Ai,j,=,当顶点,v,i,到顶点,v,j,无边时,o,o,数组存储方法,0 1 1 1,1 0 1 1,1 1 0 1,1 1 1 0,A,1,=,v,1,v,2,v,3,v,4,Vertex11:4,v,1,v,2,v,3,v,4,Vertex21:4,4,6,7,8,A,2,=,v,1,v,2,v,3,v,4,v,1,v,2,v,3,v,4,6,4,7,8,(,1,).,无向图的邻接矩阵一定是一个对称矩阵,.,(,2,).,不带权的有向图的邻接矩阵一般是一个稀疏矩阵。,(,3,).,无向图的邻接矩阵的第,i,行,(,或第,i,列,),非,0,或非,元素的个数为第,i,个顶点的度数,.,(,4,).,有向图的邻接矩阵的第,i,行非,0,或非,元素的个数为,第,i,个顶点的出度,;,第,i,列非,0,或非,元素的个数为第,i,个顶点的入度。,特点,:,除了邻接矩阵中的,n*n,个元素存储顶点间的邻接关系,外往往还需要另设一个向量存储,n,个顶点的信息。,类型定义如下,:,#define,Vnum,图的顶点数,enum,adj0,1;,typedef,adj,adjmatrixvnumvnum,;,typedef,struct,vextype,VexsVnum,;/,顶点的信息,adjmatrix,arcs;/,邻接矩阵,graph;,若图中每个顶点只含一个编号,i,则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下,:,typedef,adj,adjmatrixvnumvnum,;,无向网邻接矩阵的建立算法如下,:,思想,:,首先将矩阵,A,的每个元素都初始化为,然后,读入 边及权值,(,i,j,W,ij,),将,A,的相应元素置成,W,ij,。,算法如下,:,void build-,graph(graph,&,ga,),for(i=0;in;i+),scanf(“%d”,ga.Vexsi,);,for(i=0;i,n;i,+,),for(j=0;j,n;j,+),ga.arcsij,=,maxint,;,for(k=0;ke;,k+,)/,读入边,(,i,j,),和权,scanf(“%d,%d,%d”,i,j,w,);,ga.arcsij,=w;,ga.arcsji,=w;,二,.,邻接表存储方法,核心思想,:,对具有,n,个顶点的图建立,n,个线性链表存储该图,.,1.,每一个链表前面设置一个头结点,用来存放一个顶点的,数据信息,称之为顶点结点,.,其结构为,:,vertex,link,其中,vertex,域,存放某个顶点的数据信息,;,link,域,存放某个链表中第一个结点的地址,.,2.,第,i,个链表中的每一个链结点,(,称之为边结点,),表示以第,i,个顶点为出发点的一条边,;,边结点的构造为,next,weight,adjvex,其中,next,域为指针域,;,weight,域为权值域,(,若图不带权,则无此域,);,adjvex,域存放以第,i,个顶点为出发点的一条边,的另一端点在头结点数组中的位置,.,n,个头结点之间为一数组结构,.,1,2,3,4,v,1,v,2,v,3,v,4,4,7,8,6,1,2,3,3,(,1,).,无向图的第,i,个链表中边结点,的个数是第,i,个顶点度数,.,特,点,1,2,3,4,v,1,v,3,v,2,v,4,2,3,4,3,3,2,4,1,1,4,2,1,v,1,v,2,v,3,v,4,v,1,v,2,v,3,v,4,6,4,7,8,(2).,有向图的第,i,个链表中边结点的个数是第,i,个顶点的出度。,0,1,2,3,v,1,v,2,v,3,v,4,6,4,0,1,7,1,8,3,关于逆邻接表,v,1,v,2,v,3,v,4,6,4,7,8,(3).,有向图的逆邻接表中第,i,个链表中边结点 的个数是第,i,个顶点的入度。,#define VERNUM,图的顶点数,typedef,struct,Node,int,adjvex,;/,该弧所指向的顶点的位置,struct,Node*next;/,指向下一条弧的指针,EdgeNode,;,typedef,struct,Vnode,/,顶点结点的结构,VertexType,vertex;/,顶点信息,EdgeNode,*link;/,指向第一条依附该顶点的弧,AdjListVERNUM,;,邻接表的类型定义,思想,:(1),将邻接表表头数组初始化,第,i,个表头的,vertex,为,i,link,为,nil,。,(2),读入顶点对,产生一个表结点,将,j,放入到,adjvex,域,将该结点链到表头的,link,域上。,建邻接表,:,void build-,adjlist(AdjList,ga,),scanf(“%d,%d”,&n,&e,);/,读入顶点数，边数,e,for(i=0;in;i+)/,初始化邻接表,gai.Vertex,=i;,gai.link=Null;,for(j=0;j,e;j,+),scanf(“%d,%d”,&i,&j,);/,读入顶点对,p=new,struct,EdgeNode,;,p-,adjvex,=j;,p-next=gai.link;,gai.link=p;,邻接多重表,(Adjacency,Multilist,),在邻接多重表中,每一条边只有一个边结点。,无向图的情形,边结点的结构,mark,ivex,ilink,jvex,jlink,其中,mark,标志域，标记该边是否被搜索过,;,ivex,和,jvex,是该边两顶点位置。,ilink,指向下一条依附于顶点,ivex,的边；,jlink,指向下一条依附于顶点,jvex,的边。,顶点结点的结构,存储顶点信息的结点表以顺序表方式组织,每一个顶点结点有两个数据域：,data,存放与该顶点相关的信息，,Firstout,是指示第一条依附该顶点的边的指针。,在邻接多重表中,所有依附于同一个顶点的边都链接在同一个单链表中。,data,Firstout,从顶点,i,出发,可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。,有向图的情形,在用邻接表表示有向图时，有时需要同时使用邻接表和逆邻接表。用有向图的邻接多重表,(,十字链表,),可把这两个表结合起来表示。,边结点的结构,其中，,mark,是处理标记；,ivex,和,jvex,指明该有向边始,(,尾,),顶点和终（头）顶点的位置。,mark,ivex,jvex,ilink,jlink,ilink,是指向始顶点与该边相同的下一条边的指针；,jlink,是指向终顶点与该边相同的下一条边的指针。需要时还可有权值域,cost,。,顶点结点的结构,每个顶点有一个结点，它相当于出边表和入边表的表头结点：其中，,数据域,data,存放与该顶点相关的信息，,Firstin,指示以该顶点为头,(,箭头端,),的第一条边。,Firstout,指示以该顶点为尾,(,出边端,),的第一条边,.,data,Firstin,Firstout,邻接多重表的结构,mark vtx,1,vtx,2,path,1,path,2,0 1,0 3,1 2,2 3,3 4,4 0,e,1,e,2,e,3,e,4,e,5,e,6,data Fin,Fout,A,B,C,D,E,0,1,2,3,4,e,1,e,2,e,3,e,4,e,5,e,6,A,B,C,D,E,从图中某个指定的顶点出发,按照某一原则对图中,所有顶点都访问一次,得到一个由图中所有顶点组成的,序列,这一过程称为图的遍历,.,从图中某个指定的顶点,v,出发,先访问顶点,v,然后从顶,点,v,未被访问过的一个邻接点,W,1,出发,访问了顶点,W,1,后，再从,W,1,出发，访问和,W1,邻接且未被访问过的任意顶点,W,2,，,然后从,W,2,出发进行如上访问，重复，直到某一顶点所有邻接点都被访问过时，接着退回到尚有邻接点未被访问过的顶点，再从该顶点出发，重复上述过程，直到所有的被访问过的顶点的邻接点都已被访问为止。,一,.,深度优先搜索,图的遍历,为了标记某一时刻图中哪些顶点是否被访问,定,义一维数组,visited1:n,有,1,表示,第,i,个顶点已经被访问,visitedi,=,0,表示,第,i,个顶点还未被访问,设,g,为图的邻接表，,p,是指针，指向当前顶点。,visited,是标志向量，访问从,V1,开始，由于,V1,已访问，这时,visitedV11,再访问与,V1,邻接的顶点。于是把,V1,的表头指针送给,p,，即,pgV1-link.,当,p,所指的顶点未被访问时，则访问它,(,即调用本过程,),。否则,p,指向邻接表中的下一个结点。倘若,p,的邻接表全部访问完，则沿着原来的路径退回去。为了记录这个路径，需要设立一个栈，在由访问,Vi,的邻接表转向访问,(,调用,),Vj,的邻接表时，将,Vi,压入堆栈。而当某一个顶点的邻接表被访问完时，出栈，调用本过程。,例如：用深度优先搜索法遍历下图,。,V1,V2,V3,V4,V5,V6,V7,V8,2,3,1,4,5,1,6,7,2,8,2,8,3,8,3,8,4,5,6,7,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,V1,V2,V4,V8,V5,V6,V3,V7,现将深度优先搜索的递归算法描述如下：,void,dfs(AdjList,g,int,v1),printf(%d,gv1.vertext);,Visitedv1=1;/,标志,v0,已访问,p=gv1.link;/,找,v0,的第一个邻接点,while(p!=NULL),if(,Visitedp,-,adjvex,=0),dfs(g,p-,adjvex,);,p=p-next;,/,回溯,找,v0,的下一个邻接点,分析上述过程,在遍历图时,对图中每个顶点至多调用一次,dfs,过程，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是,对每个顶点查找其邻接点的过程。,其耗费的时间则取决于所采用的存储结构，当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为,O(n,2,),其中,n,为图中顶点数,;,而当以邻接表作图的存储结构时，查找邻接点所需时间为,O(e),，,其中,e,为无向图中的边数或有向图中弧的个数。因此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为,O(n+e),。,二,.,广度优先搜索,原则,:,从图中某个指定的顶点,v,出发,先访问顶点,v,然后依次访问顶点,v,的各个未被访问过的邻接点,W1,W2,W,t,，,然后再依次访问,W1,W2,W,t,的所有的未被访问过的邻接点，再从这些被访问的顶点出发，逐次进行访问，直到所有顶点都被访问到为止。,例如右图：,1,2,3,4,5,6,7,8,从,V1,出发，,V1,访问了,;,再访问与,V1,邻接的,V2,，,V3;,然后再访问与,V2,邻接的,V4,、,V5,，与,V3,邻接的,V6,、,V7;,再访问与,V4,邻接的,V8,则所有的顶点都被访问到了因此遍历结束。,遍历的顺序是：,V1V2V3V4V5V6V7V8,注意几个问题：,对于深度优先搜索，我们记忆出发的方向,沿来路再退回,记忆所走过的路径。,对于广度优先搜索的方法，我们用不着去记录所走过的路径。我们只需记录与每一个顶点相邻接的所有顶点，而且当访问完这些顶点时，按照先记录先搜索的方式，对被记录的顶点进行广度优先搜索。（即若,W1,在,W2,之前被访问，则,W1,的邻接点也在,W2,的邻接点之前被访问。）所以我们用一个队列,Q,来记录这些顶点是比较方便的（依次存放被访问的结点）。,和,dfs,算法一样，在这里也需要一个辅助函数,VisitedW,来标志顶点是否被访问过。,我们仍假设图用邻接表来表示。,算法,：,void,bfs(AdjList,g,int,v1),/g,表示图的邻接表，,v1,为任一顶点，,f,、,r,分别为队列的头、尾指针,Visitedv1=1;,printf(“%d,”,gv1.vertext);/,输出第一个顶点,f=0;r=0;p=gv1.link;,do,while(p!=NULL),v=p-,adjvex,;,if(,Visitedv,=0),qr,=v;r+;,printf(“%d,”,gv,.,vertext);Visitedv,=1;,p=p-next;/,找某一个顶点的所有邻接点，并进队,if(f!=,r)/v,出队,v=,qf,;f+;p=,gv.link,;,while(p!=,NULL)|(f,!=r),可以用深度优先搜索或广度优先搜索算法来判断图是否连通。,在对无向图进行遍历时：,对于连通图，仅需要一次搜索过程，图中的顶点就全部被访问。,对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰好为其各个连通分量中的顶点集。,三,.,求图的连通分量,算法,:,int,visitedvnum,;,Count_Component(Adjlist,g),int,count;,for(v,=0;v,vernum;v,+)/*,初始化,visited,数组*,/,visitedv,=0;,count=0;,for(v,=0;vV(T)=,1,做,n-1,次,1),边,(1,2),的权值最小，,将,=V(T)=,1,2,;,printf(1,2),weight 16,1,2,4,6,5,3,2),边,(2,3),的权值最小，,将,=V(T)=,1,2,3,;,printf(2,3)weight 5,3),边,(3,4),的权值最小，,将,=V(T)=,1,2,3,4,;,printf(3,4)weight 6,16,5,6,18,19,21,11,14,33,6,4),边,(2,6),的权值最小，,将,=V(T)=,1,2,3,4,6,;,printf(2,6)weight 11,5),边,(4,5),的权值最小，,将,=V(T)=,1,2,3,4,5,6,;,printf(4,5)weight 18,i=1,6,Weight =56,18,1,2,4,6,5,3,16,5,6,19,21,11,14,33,6,1,2,4,6,5,3,16,5,6,18,11,最短路径问题,.,路径长度的定义,1,.,不带权的图,:,路径上所经过的边的数目,。,2,.,带权的图,:,路径上所经过的边上的权值之和,.,.,问题的提出,设,出发顶点为,v,(,通常称为源点,),。确定源点到其他各顶点的,最短路径，常应用于选择路线，架设电线等,一。从源点到其余各顶点间的最短路径,0,1,3,5,2,4,45,50,10,20,10,15,15,20,3,35,30,v0,是源点 最短路径,v0v2 10,v0v2v3 10+15=25,v0v2v3v1 10+15+20,v0v4 45,v0v5,无路可走,从以上可以发现每一条最短路径中间所经过的顶点具有如下特点：下一条最短路径,(,设其终点为,x),可能是,或者,，而,u,v,都是已求得的最短路径终点。,例,设,S,为已求得的最短路径的终点的集合,(S,初态为空集,),，则下一条长度次短的最短路径（设终点为,x,）：,或者是弧,；,或者是中间经过,S,集合中顶点，最后到达顶点,x,的路径。,以上是,迪杰斯特拉,(,dijkstra,),提出的按路径长度递增的次序产生最短路径的思想。,按长度递增的次序产生最短路径，需设一个辅助向量,distw,，,它的每一个分量,distw,表示当前找到的从,v0,到终点,w(wV(G),的最短路径长度。,初态为,distw=,弧上的权值 从,v0,到,w,有弧,从,v0,到,w,无弧,那么下一条长度次短的最短路径用公式描述为：,distx=,上的权值,E(G),distu+,上的权值,E(G),中间经过,S,集合中的顶点,u,最后到达顶点,x,的路径,下面给出算法思想：,b),而,=0,，设,S,为已找到从,v,0,出发的最短路径的终点的 集合,它的,初态为源点（,v,0,),。,c),设从,v0,出发到,G,中其余各顶点,(,终点,),v,i,的最短路径长度为：,初态,disti=costv,0,v,i,V,i,V(G),选择,u,，使,distu=Min,disti|v,i,不属于,S,v,i,V(G),（则,u,为目前求得的一条从,v,0,出发的最短路径的终点）,令,S=S,u,（,u,进入,s,）,设,cost,为带权的邻接矩阵,a)cost=,上的权值,(i,j,之间有弧,),(i,j,之间无弧,),修改所有不在,S,的终点的最短路径的长度，若,distu+costui,disti,，,则修改,disti,为,disti=,distu+costui,同时修改相应的路径,.,重复操作,共,n-1,次，由此求得从,v,0,到,G,中其余各顶点的最短路径是依路径长度递增的序列。,给出算法：,void,shortpath(adjmatrix,costvernumvernum,int,v0),/,求从源点,v0,到其它各顶点的最短路径,cost,为有向图的带权邻接矩阵，,v0,为其中某个顶点的编号；,disti,为当前找到的从,v0,到,i,的最短路径长度,pathi,为相应的路径；,max,为计算机内允许的最大值,for(i=0;in;i+),disti,=costv0i;,if(,disti,max),pathi,=v0+i;/,表示集合，,+,表示集合运算，表示两个集合相并,else,pathi,=;/,表示为空集,/,建立,dist,及,path,的初态,s=v0;num=0;/s,为已找到最短路径的终点的集合,while(numn-1),wm=max;u=v0;,for(i=0;in;i+),/,选,disti,的最小值,if(!(i in s)/,若不属于,s,if(,disti,wm),u=,i;wm,=,disti,;,/,按,disti,的最小值选取了,u,s=,s+u,;/,将,u,加入最短路径的终点集合,s,for(i=0;in;i+)/,修改,dist,和,past,的值,if(!(i in s)/,若,i,不属于,s,if(,distu+costui,disti,),disti,=,distu,+,costui,;,pathi,=,pathu+i,;,num+;,算法执行时间：第一个,FOR,循环是,O(n),，,接下来循环共进行,n-1,次，每一次执行时间是,O(n),，,所以总的时间为,O(n,2,),。,二、,每一对顶点间的最短路径,Floyed,算法思想：,从,i,到,j,的路径上每次增加一个结点,k,，,看这个增加了一个结点,k,的新路径的长度是否比原来的路径长度小，若小,则以新路径代之,否则保持原路径。,A,(k),ij,=minA,(k-1),ij,A,(k-1),ik+A,(k-1),kj(1,kn),算法计算公式：,其中,:,A,(k),ij,表示顶点,i,j,之间的中间点的序号不大于,k,的最短距离,;,由于,G,中顶点编号不大于,n,，,所以最后到了,A,n,ij,就代表,i,到,j,的最短路径之长。,算法描述：,void,allpths(cost,),for(i,=1;i=,n;i,+),for(j,=1;j=,n;j,+),aij,=,costij,;,if(i!=,j)&(aij,max),pathij,=,i+j,/,建立了,A(0),和,path(0),即,A,和,path,的初始矩阵,for(k,=1;k=,n;k,+),for(i,=1;i=,n;i,+),for(j,=1;j=,n;j,+),if(aik+akj,aij,),aij,=,aik+akj,;,pathij,=,pathjk+pathkj,;,cost=,0 4 11,6 0 2,3 0,cost:,带权邻接矩阵,A,：,最短路径长度,P,：,相应的路径,例：,6,4,11,3,2,A,B,C,3,2,1,初态,K=0,时，,A,(0),1 2 3,1,2,3,0 4 11,6 0 2,3 0,AB AC,Path,(0),1 2 3,1,2,3,BA BC,CA,K=1,时，,A,(1),1 2 3 Path,(1),1 2 3,1 0 4 11 1 AB AC,2 6 0 2 2 BA BC,3 3,7,0 3 CA,CAB,K=2,时，,A,(2),1 2 3 Path,(2),1 2 3,1 0 4,6,1 AB,ABC,2 6 0 2 2 BA BC,3 3,7,0 3 CA,CAB,K=3,时，,A,(3),1 2 3 Path,(3),1 2 3,1 0 4,6,1 AB,ABC,2,5,0 2 2,BCA,BC,3 3,7,0 3 CA,CAB,一,.,AOV,网的定义,在,AOV,网中，若顶点,i,到顶点,j,之间有有向路径，,则称顶点,i,为顶点,j,的前驱，顶点,j,为顶点,i,的后继；若,顶点,i,到顶点,j,之间为一条有向边，则称顶点,i,为顶点,j,的直接前驱，顶点,j,为顶点,i,的直接后继。,以顶点表示活动，以有向边表示活动之间的优先,关系的有向图称为,AOV,网。,AOV,网与拓扑排序,程序,语言,数据,结构,离散,数学,软件,工程,操作,系统,编译,原理,数据库,计算机,组成,汇编,网络,数字,逻辑,计算机,导论,例,如,二,.,拓扑排序,介绍一下,拓扑有序,(topological order),的概念：对一个网构造顶点的线性序列，使得在此序列中不仅保持有向图中原有的顶点之间的先后关系，而且对有向图中所有没有关系的两个顶点之间也建立一个先后关系，称具有上述特性的线性序列为,拓扑有序序列,。,构造拓扑有序序列的过程称为,拓扑排序,拓扑排序方法,1,.,从,AOV,网中任选择一个没有前驱,(,入度为,0,),的顶点,；并把它输出；,2,.,从,AOV,网中删除该顶点以及所有以该顶点为尾的边；,3,.,重复上述过程,，,直到网中所有顶点都被输出,或者网中,剩余的顶点中有前趋顶点，而不能继续执行了。前一种情况说明工程是可行的，后一种情况说明网络中有环，工程不可行。,v,1,v,4,v,3,v,2,v,6,v,5,v,7,v,1,v,5,v,7,v,3,v,6,v,2,v,4,例,v,4,v,3,v,2,v,6,v,7,v,4,v,3,v,2,v,6,v,5,v,7,v,4,v,3,v,2,v,7,v,4,v,3,v,7,v,4,v,7,v,7,有向图,为完成拓扑排序,采用如下邻接表为存储结构,此种链表可由计算机自动建立,:,V1,V2,V3,V4,V5,V6,0,2,1,2,3,0,4,3,2,5,5,2,5,4,算法思想,：建立一个栈（这个栈存放入度为,0,的结点）检查邻接表，将所有入度为零的顶点送栈，随后输出入度为,0,的顶点。,Vj,输出时,将,Vj,的直接后继,Vk(k,=1,2,),的入度减,1,，并将入度减到零的顶点进栈。当栈为空时，则检查一下是否输出了有向图的全部顶点（,n,个）：若是，则排序结束；反之，则网中有环。,一个好的算法，一般在时空两个方面都应尽量的节约，对于拓扑排序算法，我们可以另开辟一块空间作为栈，还可以想办法利用它现有的存储空间，形成一个链栈。,while(top,!=0),j=,top;top,=,gtop.in,;/,退栈,printf(“v%d”,j,);,m+;/,输出顶点并计数,q=,gj.link,;/q,是指针，指示以,j,为尾的弧,算法如下：,void,toposort(AdjList,g),/,有向图,g,是邻接表存储，表头中每个分量有三个域,data,next,in,(,入度,),对入度为,0,的顶点设计链栈，,top,指示栈顶元素,.,readlist,();/,输入,e,条弧并建立邻接表,top=0;,for(i,=1;i,adjvex,;/,顶点,k,为,j,的直接后继,gk.in,=gk.in-1;/,入度减,1,if(,gk.in,=0),gk.in,=top;top=k;/,入度为零的顶点进栈,q=q-next;,if(mn),printf(“the,network have cycle”);,/,输出顶点数不足,n,，说明网中有环,算法分析,：,假设有向图有,n,个顶点，,e,条边，那么建立邻接表的执行时间为,O(e),；,搜索入度为,0,的时间为,O(n),；,在拓扑排序过程中，若有向图无环，则每个顶点进一次栈，入度减,1,的运算在,WHILE top0,的语句中共执行,e,次，所以总的执行时间为,O(n+e),。,一,.,AOE,网的定义,AOE,网为一个带权的有向无环图，其中，顶点表示事,件，有向边表示活动，边上的权值表示活动持续的时间。,a,4,v,1,v,4,v,2,v,3,v,5,v,7,v,9,v,8,v,6,a,1,a,2,a,3,a,5,a,6,a,7,a,8,a,9,a,10,a,11,6,4,5,1,1,2,9,7,2,4,4,正常情况下，,AOE,网中只有一个入度为,0,的顶点，称,之为,源点,；有一个出度为,0,的顶点，称之为,终点,。,AOE,网与关键路径,1,.,只有在某个顶点所代表的事件发生以后,该顶点引发的,活动才能开始。,2,.,进入某事件的所有边所代表的活动都已完成,该顶点所,代表的事件才能发生。,AOE,网的特点,：,1.,关键路径的定义,从,源点到,终点的路径中具有,最大路径长度的路径,为,关键路径,;,关键路径上的活动称为关键活动。,二,.,关键路径,2,.,关键路径的特点,1),关键路径的长度,(,路径上的边的权值之和,),为,完成整,个工程所需要的最短时间,。实际上为,最长路径之长,.,2,),关键路径的长度变化,(,即任意关键活动的权值变化,),将影响整个工程的进度，而其他非关键活动在一定,范围内的变化不会影响工期。,3.,求关键活动的思路：,e(i),活动,a,i,的,最早开始时间,l(i),活动,a,i,的,最迟开始时间,若,l(i),a(i)=0,，,则说明活动,a,i,为,一个关键活动。,Ve(j,),事件,j,的最早发生时间,Vl(j,),事件,j,的最迟发生时间,k,a,i,j,事件,j,的最早发生时间,ve(j,),事件,j,的最迟发生时间,v,l(j,),活动,a,i,的,最早开始时间,e(i),活动,a,i,的,最,迟,开始时间,l(i),求,e(i)=l(i),结论,1).,计算事件,j,的最早发生时间,Ve(j,),所谓事件,j,的最早发生时间,Ve(j,),是指从源点到顶点,j,的最大路径长度,.,ai,计算方法,:,Ve(1)=0,Ve(j,)=,Max,Ve(i,)+,的权,P(j),i,j,k,利用此公式前例可求得：,Ve(j,)j=2,9,已知,Ve(1)=0,Ve(2)=0+dut(a1)=6 Ve(3)=0+dut(a2)=4,Ve(4)=0+dut(a3)=5 Ve(5)=Ve(2)+dut(a4)=6+1=7,=Ve(3)+dut(a5)=4+1=5,Ve(6)=Ve(4)+dut(a6)=5+2=7,Ve(7)=Ve(5)+dut(a7)=7+9=16,Ve(8)=Ve(5)+dut(a8)=7+7=14,Ve(9)=Ve(7)+dut(a10)=16+2=18,=Ve(8)+dut(a11)=14+4=18,求,Ve(j,),：,是在,j,的所有前趋顶点的最早开始时间求得后才进行计算。如果我们将所有的顶点进行拓扑分类，按顶点的拓扑次序依次求出各个事件的最早出现时间将是十分方便的，因此我们利用拓扑排序的算法求得,Ve(j,),在,2).,计算事件,j,的最迟发生时间,Vl(j,),所谓事件,j,的最晚发生时间,Vl(j,),是指不影响整个工,期的前提下事件,j,必须发生的最晚时间。,计算方法,:,Vl(n,)=,Ve(n,),Vl(j,)=,Min,Vl(k,),的权,S(k),toposort,算法中,插入,Ve(j,)=max,Ve(i)+dut,(),到入度减后边即可,例,上例,的,Vl(j,)i=9,1,为,已知,V(9)=Ve(9)=18,Vl(8)=Vl(9)-dut(a11)=18-4=14,Vl(7)=Vl(9)-dut(a10)=18-2=16,Vl(6)=Vl(8)-dut(a9)=14-4=10,Vl(5)=Vl(8)-dut(a8)=14-7=7,=Vl(7)-dut(a7)=16-9=7,Vl(4)=Vl(6)-dut(a6)=10-2=8,Vl(3)=Vl(5)-dut(a5)=7-1=6,Vl(2)=Vl(5)-dut(a4)=7-1=6,Vl(1)=Vl(4)-dut(a3)=8-5=3,=Vl(3)-dut(a2)=6-4=2,=Vl(2)-dut(a1)=6-6=0,求,Vl(j,):,事件,j,的最迟发生时间能够计算之前，对,事件,j,所有的后继事件（即由,j,邻接到的事件例如,k,）,的最迟发生时间必须计算出来，这些后继事件的最迟发生时间能够利用类似于求,Ve(j,),的办法求得，但此时必须把图用逆邻接表表示，表头结点的数据域中存放顶点出度的信息。,在,toposort,算法中插入的,Vl(j,):=min,Vl(k)-dut,(,s 1in-1,即可求得,Vl(j,)i=9,8,7,1,3).,计算活动,i,的最早开始时间,e(i),所谓活动,i,的最早开始时间,e(i),是事件,j,发生的最早时,间，即只有事件,j,发生了，活动,i,才能开始。,活动,i,j,k,计算方法：,e,(i)=,Ve,(j,),4).,计算活动,i,的最迟开始时间,l(i),所谓活动,i,的最迟开始时间,l(i),是指不推迟整个工期,的前提下活动,i,开始的最晚时间。,计算方法：,l(i)=,vl(k,),-,的权,活动,i,j,k,我们的目的是求网的关键路径，但必须要求出,e(i),和,l(i),而要求,e(i),和,l(i),就必须要求出,Ve(j,),和,Vl(j,);,而要求出,Ve(j,),和,Vl(j,),则必须要建立邻接表和逆邻接表,这样的话,未免有些浪费存储单元。因此对于此问题一般是取十字链表作为网的存储结构。在十字链表中，每个结点表示一条弧，它由,5,个域组成：,tail,head,dut,hlink,tlink,tail:,弧的尾顶点,j,head:,弧的头顶点,k,dut,:,是活动,ai,的持续时间,hlink,:,链接以,k,为头的另一条弧,tlink,:,链接以,j,为尾的另一条弧,另设一个由,n,个表头结点组成的向量，每个表头结点表