图是一种比线性表和树更为复杂的数据结构解读课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020-5-30,谢谢阅读,2020-5-30,谢谢阅读,1,第七章 图,图是一种比线性表和树更为复杂的数据结构。在图中，元素间的关系是多对多的，即任何两个元素都有可能存在关系。,图的应用非常广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中,(,日常生活中的交通图等,),。,在离散数学中，图论是专门研究图的性质的数学分支。,在数据结构中对图的讨论主要侧重于图在计算机中的存储方式和有关操作的算法。,2020-5-30,谢谢阅读,2,图的基本内容,7.1,图的定义和术语,7.2,图的存储结构,7.3,图的遍历,7.4,图的连通性问题,7.5,有向无环图及其应用,7.6,最短路径,2020-5-30,谢谢阅读,3,7.1,图的定义和术语,抽象数据类型图的定义：,ADT Graph ,数据对象,V: V,是具有相同特性的数据元素的集合，称为顶点集。,数据关系,R: R=VR,VR=|v,w,V,且,P(v,w),表示从,v,到,w,的弧，谓词,P(v,w),定义了弧,的意义或信息,基本操作,P: CreateGraph,DestroyGraph,LocateVex,GetVex,PutVex,FirstAdjVex,NextAdjVex,InsertVex,DeleteVex,InsertArc,DeleteArc,DFSTraverse,BFSTraverse,ADT Graph,2020-5-30,谢谢阅读,4,图的定义,(,续,),图中的数据元素称为,顶点,(vertex),V,是顶点的有穷非空集合；,VR,是,V,上顶点的序偶或无序对的集合。,若,VR,，则,表示从,v,到,w,的一条弧,(Arc),且称,v,为弧尾,(Tail),或初始点,(Initial node),称,w,为弧头,(Head),或终端点,(Terminal node),此时的图称为,有向图,(Digraph),。,若,VR,必有,VR,，即,VR,是对称的，则以无序对,(v,w),代替两个有序对，表示,v,和,w,之间的一条,边,(Edge),此时的图称为,无向图,(Undigraph),。可以说图由非空顶点集和边集所组成。,2020-5-30,谢谢阅读,5,图的示例,无向图,G,1,有向图,G,2,图的二元组表示参见教材,P,157,2020-5-30,谢谢阅读,6,图的基本术语,完全图、稠密图、稀疏图,约定：用,n,表示图中顶点的数目，用,e,表示边或弧的数目,若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为,完全图,。,当一个图接近完全图时，称为,稠密图,。,当一个图含有较少的边或弧,(e0),for (i=1;i=num;i+),for (j=1;j=num;j+),adjarry ij=0; /*,矩阵初始化,*/,do,2020-5-30,谢谢阅读,15,产生无向图邻接矩阵算法续,scanf (“%d,%d”, /*,输入边,*/,adjarrayv1v2=1;,adjarrayv2v1=1;, while(v1!=0 ,else,num=0;,retrun num;,2020-5-30,谢谢阅读,16,邻接表,邻接表是图的一种链式存储结构。,在邻接表结构中，对图中每个顶点建立一个单链表，第,i,个单链表中的结点表示依附于该顶点,V,i,的边，即对于无向图每个结点表示与该顶点相邻接的一个顶点；对于有向图则表示以该顶点为起点的一条边的终点。,一个图的邻接矩阵表示是唯一的，但其邻接表表示是不唯一的。因为在邻接表的每个单链表中，各结点的顺序是任意的。,2020-5-30,谢谢阅读,17,无向图、有向图,2020-5-30,谢谢阅读,18,无向图的邻接表,2020-5-30,谢谢阅读,19,有向图的邻接表,2020-5-30,谢谢阅读,20,邻接表中每个表结点均由两个域组成，其一是邻接点域（,adjvex,），用以存放与顶点,V,i,相邻接的顶点在图中的位置；其二是链域（,next,），用以指向依附于顶点,V,i,的下一条边所对应的结点。,如果用邻接表存放网络中的信息，则还需要在结点中增加一个存放权值的域。,在每个链表设一表头结点，一般这些表头结点本身以向量的形式存储。,邻接表的若干说明,2020-5-30,谢谢阅读,21,对于无向图的邻接表来说，一条边对应两个单链表结点，邻接表结点总数是边数的,2,倍。,在无向图的邻接表中，各顶点对应的单链表的结点数（不算表头结点）就等于该顶点的度数。,在有向图邻接表中，一条弧对应一个表结点，表结点的数目和弧的数目相同。,在有向图邻接表中，单链表的结点数就等于相应顶点的出度数。,要求有向图中某顶点的入度数，需扫视邻接表的所有单链表，统计与顶点标号相应的结点个数。,邻接表的若干说明,2020-5-30,谢谢阅读,22,邻接表存储结构定义,#define MAXVEX 30,struct edgenode, int adjvex ; /*,邻接点域,*/,struct edgenode *next ; /*,链域,*/,;,struct vexnode, char data; /*,顶点信息,*/,struct edgenode *link;,;,typedef struct vexnode adjlistMAXVEX;,2020-5-30,谢谢阅读,23,生成无向图的邻接表算法,void creategraph (adjlist g),int e,i,s,d,n;,struct edgenode *p;,printf(“,请输入结点数,(n),和边数,(e):n”);,scanf(“%d,%d”,for(i=1;i=n;i+),printf(“n,请输入第,%d,个顶点信息：”,i);,scanf(“%c”,gi.link=NULL;,for(i=1;i=e;i+),2020-5-30,谢谢阅读,24,生成无向图的邻接表算法续,printf(“n,请输入第,%d,条边起点序号，终点序号：”,i);,scanf(“%d,%d”,p=(struct edgenode *)malloc(sizeof(edgenode);,padjvex=d; /*,邻接点序号为,d*/,pnext=gs.link;,gs.link=p;,/*,将新结点插入顶点,V,s,边表的头部,*/,p=(struct edgenode *)malloc(sizeof(edgenode);,padjvex=s; /*,邻接点序号为,s*/,pnext=gd.link;,gd.link=p; /*,将新结点插入顶点,V,d,边表的头部,*/,2020-5-30,谢谢阅读,25,十字链表和邻接多重表简介,十字链表是将有向图的邻接表和逆邻接表结合起来得到的一种链表。,邻接多重表是无向图的另一种链式存储结构。在邻接多重表中，每一条边用一个结点表示，它由五个域组成；每一个顶点也用一个结点表示，它由两个域组成。,2020-5-30,谢谢阅读,26,思考题,1.,已知如下图所示的有向图，请给出该图的,（,1,）每个顶点的入,/,出度；,（,2,）邻接矩阵；,（,3,）邻接表。,1,5,6,2,4,3,2020-5-30,谢谢阅读,27,7.3,图的遍历,从图中某一顶点出发访遍图中其余结点，且使每一个顶点仅被访问一次，这一过程称为图的遍历,(Traversing Graph).,图的遍历算法是求解图的连通性、拓扑排序和求关键路径等算法的基础。,为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。,图的遍历有两种：深度优先搜索和广度优先搜索。,2020-5-30,谢谢阅读,28,深度优先搜索,(DFS),类似于树的先根遍历，是树的先根遍历的推广。,首先访问图中某指定起始点,V,i,，然后由,V,i,出发访问它的任一相邻接顶点,V,j,再从,V,j,出发访问,V,j,的任一未访问过的相邻接顶点,V,k,再从,V,k,出发进行类似访问，如此进行下去，直到某顶点已没有未被访问过的相邻接顶点时，则退回一步，退到前一个顶点，找前一个顶点的其它尚未被访问的相邻接顶点。,如有未访问过的相邻接顶点，则访问此顶点后，再从该顶点出发向前进行与前述类似的访问；,如退回一步后，前一顶点也没有未被访问过的相邻接顶点，则再向回退一步进行搜索，重复上述过程，一直到所有顶点均被访问过为止。,2020-5-30,谢谢阅读,29,图的深度优先遍历例子,深度优先遍历序列：,1 2 4 8 5 3 6 7,2020-5-30,谢谢阅读,30,由于图中的路径可能有环路，为了避免重复访问某些顶点，设计图的搜索算法时，可设置一个表示顶点是否被访问过的辅助数组,visited,，初始时将数组元素置零，一旦某顶点,V,i,被访问过，则令,visitedV,i,=1,，以后此顶点即不再访问。,深度优先搜索算法,2020-5-30,谢谢阅读,31,深度优先搜索算法,深度优先搜索是一种递归的过程，可以简单地将其表示成递归的形式，其算法描述如下：,DFS(V,0,),访问,V,0,顶点,;,visitedV,0,=1;,对所有与,V,0,相邻接的顶点,w,if (visitedw=0),DFS(w);,2020-5-30,谢谢阅读,32,邻接表表示的图的,DFS,算法,int visitedMAXVEX;,void dfsgraph(adjlist adj, int n),int i;,for(i=1;i=n;i+),visitedi=0; /*,给,visited,数组赋初值,*/,for(i=1;i=n;i+),if(!visitedi),dfs(adj, i);,2020-5-30,谢谢阅读,33,邻接表存储结构定义,#define MAXVEX 30,struct edgenode, int adjvex ; /*,邻接点域,*/,struct edgenode *next ; /*,链域,*/,;,struct vexnode, char data; /*,顶点信息,*/,struct edgenode *link;,;,typedef struct vexnode adjlistMAXVEX;,2020-5-30,谢谢阅读,34,从,V,i,出发进行,DFS,的递归算法,void dfs(adjlist adj,int v), struct edgenode *p;,visitedv=1;,printf(“%d”,v);,p=adjvlink;,while(p!=NULL), if(visitedpadjvex=0),dfs(adjlist,padjvex);,/*,从,v,未访问的邻接点出发进行,DFS*/,p=pnext;,2020-5-30,谢谢阅读,35,时间复杂性分析,一个有,n,个顶点、,e,条边的图，在深度优先搜索图的过程中，找邻接点所需时间为,O(e),。,对辅助数组初始化时间为,O(n),。,因此，当用邻接表作为图的存储结构时，深度优先搜索图的时间复杂性为,O(e+n),。,2020-5-30,谢谢阅读,36,非递归算法,从顶点,V,i,出发进行深度优先遍历的递归过程也可以写成非递归的形式，此时需借助一个堆栈保存被访问过的结点，以便回溯时查找已被访问结点的未被访问过的邻接点。,设堆栈由一个一维数组构成，数组名为,stack,，栈顶指针为,top ,假设此数组足够大,不必考虑溢出的可能。,2020-5-30,谢谢阅读,37,非递归算法,#define MAXVEX 100,void dfs(adjlist g,，,int v,int n),/*,从顶点,v,出发进行深度优先遍历,*/,struct vexnode *stackMAXVEX, *p;,int visitedMAXVEX,top=0;,for(i=1;i0|p!=NULL),2020-5-30,谢谢阅读,38,非递归算法续,while(p!=NULL),if (visitedp-adjvex=1),p=p-next;,else,printf(“%d”,p-adjvex);,visitedp-adjvex=1;,top+;,stacktop=p;,p=gp-adjvex.link;,2020-5-30,谢谢阅读,39,非递归算法续,if(top0),top-;,/*,退栈，回溯查找已被访问结点的未被访问过的邻接点,*/,p=stacktop;,p =p-next;,2020-5-30,谢谢阅读,40,广度优先搜索,(BFS),图的广度优先搜索（,BFS,）类似于树的按层次遍历。,广度优先搜索的基本思想是：首先访问图中某指定的起始点,V,i,并将其标记为已访问过，然后由,V,i,出发访问与它相邻接的所有顶点,V,j,、,V,k,，并均标记为已访问过，然后再按照,V,j,、,V,k,的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止。,2020-5-30,谢谢阅读,41,广度优先搜索,(,续,),在广度优先搜索中，若对顶点,V,1,的访问先于顶点,V,2,的访问，则对,V,1,邻接顶点的访问也先于,V,2,邻接顶点的访问。就是说广度优先搜索中对邻接点的寻找具有“先进先出”的特性。因此，为了保证访问顶点的这种先后关系，需借助一个队列暂存那些刚访问过的顶点。,设此队列由一个一维数组构成，数组名为,Queue,，队首指针和队尾指针分别为,front,和,rear,。假设数组足够大，不必考虑有溢出的可能性。,广度优先搜索不是递归过程，不能用递归形式。,2020-5-30,谢谢阅读,42,图的广度优先遍历例子,广度优先遍历序列：,1 2 3 4 5 6 7 8,2020-5-30,谢谢阅读,43,图的遍历举例,已知一有向图的邻接表存储结构如下页图所示，分别给出从顶点,v1,出发进行深度优先和广度优先遍历所得到的顶点序列。,2020-5-30,谢谢阅读,44,一个有向图的邻接表,2020-5-30,谢谢阅读,45,例子解答,解：根据有向图的深度优先遍历算法，从顶点,v1,出发所得到的顶点序列是：,v1,，,v3,，,v4,，,v5,，,v2,根据有向图的广度优先遍历算法，从顶点,v1,出发所得到的顶点序列是：,v1,，,v3,，,v2,，,v4,，,v5,2020-5-30,谢谢阅读,46,BFS,算法描述,BFS(v0),访问,v0,顶点；,visitedv0=1;,被访问过的顶点入队；,当队列非空时，进行下面的循环,（,1,）被访问过的顶点出队；,（,2,）对所有与该顶点相邻接的顶点,w,if (visitedw=0), (a),访问,w,顶点；,(b)visitedw=1;,(c)w,入队,;,2020-5-30,谢谢阅读,47,时间复杂性分析,一个有,n,个顶点、,e,条边的图，在广度优先搜索图的过程中，每个顶点至多进一次队列，图的搜索过程实质上是通过边来找顶点的过程，找邻接点所需时间为,O(e),。,对辅助数组初始化时间为,O(n),。,因此，当用邻接表作为图的存储结构时，广度优先搜索图的时间复杂性为,O(e+n),。,2020-5-30,谢谢阅读,48,7.4,图的连通性问题,无向图的连通分量和生成树,深度优先搜索或广度优先搜索在遍历无向图时，若无向图是连通图，则从图中任一顶点出发，便可访问到图中所有顶点。若无向图是非连通图，则需从多个顶点出发进行搜索，每次调用搜索过程得到的顶点访问序列恰为其各个连通分量中的顶点集。,遍历过程中经过的边的集合和图中所有顶点一起构成连通图的极小连通子图，为连通图的一棵生成树。分别有深度优先生成树和广度优先生成树。,2020-5-30,谢谢阅读,49,生成树的进一步描述,在一个无向连通图,G,中，如果取它的全部顶点和一部分边构成一个子图,G,，若边集,E(G,),中的边刚好将图的所有顶点连通但又不形成环路，我们就称子图,G,是原图,G,的生成树（,Spanning tree,）。,生成树有如下特点：任意两个顶点之间有且仅有一条路径；如果再增加一条边就会出现环路；如果去掉一条边此子图就会变成非连通图。,一个有,n,个顶点的完全图，一共存在,n,(n-2),种不同的生成树。,2020-5-30,谢谢阅读,50,非连通图的生成森林,对于非连通图，每个连通分量中的顶点集，和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。,生成树和生成森林除依赖于遍历算法外，还依赖于采用的存储结构。,2020-5-30,谢谢阅读,51,最小生成树,对于带权的连通图（连通网）,G,，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为最小生成树（,Minimum Spanning Tree,）。,具有,n,个顶点的连通图的生成树具有,n-1,条边（少于此边数不可能将各顶点连通，多于此边数则必然要出现环路） 。,2020-5-30,谢谢阅读,52,无向连通图,G,及其生成树,无向连通图,G,生成树,2020-5-30,谢谢阅读,53,图,G,的,其它生成树,生成树,最小生成树,2020-5-30,谢谢阅读,54,普里姆,(prim),算法描述,假设,G=(V,E),是一个具有,n,个顶点的连通网络，,T=(U,TE),是,G,的最小生成树，其中,U,是,T,的顶点集，,TE,是,T,的边集，,U,和,TE,的初值均为空。,算法开始时，首先从,V,中任取一个顶点（假定为,V,1,），将此顶点并入,U,中，此时最小生成树顶点集,U=V,1,；,然后从那些其一个端点已在,U,中，另一个端点仍在,U,外的所有边中，找一条最短（即权值最小）的边，假定该边为,(V,i,V,j,),其中,V,i,U,，,V,j,V-U,并把该边,(V,i,V,j,),和顶点,V,j,分别并入,T,的边集,TE,和顶点集,U,；,2020-5-30,谢谢阅读,55,普里姆,(prim),算法描述续,如此进行下去，每次往生成树里并入一个顶点和一条边，直到,n-1,次后，把所有,n,个顶点都并入生成树,T,的顶点集,U,中，此时,U=V,，,TE,中包含有（,n-1,）条边；,这样，,T,就是最后得到的最小生成树。,普里姆算法中每次选取的边两端，总是一个已连通顶点（在,U,集合内）和一个未连通顶点（在,U,集合外），故这个边选取后一定能将未连通顶点连通而又保证不会形成环路。,2020-5-30,谢谢阅读,56,普里姆算法例子,2020-5-30,谢谢阅读,57,普里姆算法,为了便于在顶点集合,U,和,V-U,之间选择权最小的边，建立两个数组,closest,和,lowcost,closesti,表示,U,中的一个顶点，该顶点与,V-U,中的一个顶点构成的边具有最小的权；,lowcost,表示该边对应的权值。,开始，由于,U,的初值为,1,，所以，,closesti,的值为,1,，,i=2,n,而,lowcosti,为,V,1,到各顶点的边中最小的权值。,2020-5-30,谢谢阅读,58,算法分析,该算法中每一步执行都要扫描数组,lowcost,，在,V-U,顶点集中找出与,U,最近的顶点，令其为,k,，并打印边（,k,closestk,）。,然后将,k,加入,U,顶点集合中，并修改数组,lowcost,和,closest,。,这里用,c,表示图的邻接矩阵，,cij,和,cji,是边,(i,j),的权。,2020-5-30,谢谢阅读,59,克鲁斯卡尔（,Kruskal,）算法,假设,G =,（,V,，,E,）是一个具有,n,个顶点的连通网络，,T=(U,TE),是,G,的最小生成树，,U,的初值等于,V,，即包含有,G,中的全部顶点，,TE,的初值为空集。,基本思想：将图,G,中的边按权值从小到大的顺序依次选取，若选取的边使生成树,T,不形成环路，则把它并入,TE,中，保留作为生成树,T,的一条边，若选取的边使生成树,T,形成环路，则将其舍弃，如此进行下去，直到,TE,中包含,n-1,条边为止。此时的,T,即为最小生成树。,2020-5-30,谢谢阅读,60,克鲁斯卡尔算法例子,(a),带权图,2020-5-30,谢谢阅读,61,(c),最小生成树,2020-5-30,谢谢阅读,62,克鲁斯卡尔算法续,在选取某边时如何判断是否与已保留的边形成环路？克鲁斯卡尔算法是通过将各顶点划分为集合的办法来解决的。,开始时假定,n,个顶点分属于,n,个集合,即每个集合中有一个顶点,当确定某条边保留作为生成树的一条边时,就将该边两端点所属的两集合合并为一个,表示原来属于两个集合的各个顶点已被这条新的边连通,.,如果取到某条边,发现它的两个端点已属于同一集合时,此边则应当舍去,.,因为两个顶点属于同一集合说明它们已连通,若再添上这条边就会出现环路。,如此进行下去，到所有的顶点均已属于一个集合时，此最小生成树就构成了。,2020-5-30,谢谢阅读,63,7.5,有向无环图及其应用,在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：,先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；,子项目之间无次序要求，即两个子项目可以同时进行，互不影响。,在工厂中，一件设备的生产包括许多工序，各工序之间也存在这两种关系。,学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。,2020-5-30,谢谢阅读,64,AOV,网络,这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个个顶点称之为活动,(Activity),。,如果从顶点,V,i,到,V,j,之间存在有向边,则表示活动,i,必须先于活动,j,进行。这种图称做顶点表示活动的网络,(Activity On Vertex network,简称,AOV,网络,),。,例如某校计算机专业的课程及其相互之间的关系，它对应的,AOV,网络如下页图所示。,2020-5-30,谢谢阅读,65,某专业课程设置,2020-5-30,谢谢阅读,66,课程设置的,AOV,网络,2020-5-30,谢谢阅读,67,有向无环图描述,在,AOV,网络中，如果顶点,V,i,的活动必须在顶点,V,j,的活动以前进行，则称,V,i,为,V,j,的前趋顶点，而称,V,j,为,V,i,的后继顶点。这种前趋后继关系有传递性。,AOV,网络中一定不能有有向环路。例如在下页图那样的有向环路中，,V,2,是,V,3,的前趋顶点，,V,1,是,V,2,的前趋顶点，,V,3,又是,V,1,的前趋顶点，环路表示顶点之间的先后关系进入了死循环。,因此，对给定的,AOV,网络首先要判定网络中是否存在环路，只有有向无环路网络在应用中才有实际意义。,一个无环的有向图称为,有向无环图,，它是一类较有向树更一般的特殊有向树。,2020-5-30,谢谢阅读,68,有向环路举例,2020-5-30,谢谢阅读,69,拓扑排序,所谓“,拓扑排序,”就是将,AOV,网络中的各个顶点,(,各个活动,),排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得到满足。,由于,AOV,网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。,通过拓扑排序还可以判断出此,AOV,网络是否包含有有向环路，若有向图,G,所有顶点都在拓扑排序序列中，则,AOV,网络必定不包含有有向环路。,2020-5-30,谢谢阅读,70,拓扑排序方法,(1),在网络中选择一个没有前趋,(,入度为,0),的顶点，并把它输出；,(2),从网络中删去该顶点和从该顶点发出的所有有向边；,(3),重复执行上述两步，直到网中所有的顶点都被输出,(,此时，原,AOV,网络中的所有顶点和边就都被删除掉了,),。,如果进行到某一步，无法找到无前趋的顶点，则说明此,AOV,网络中存在有向环路，遇到这种情况，拓扑排序就无法进行了。,2020-5-30,谢谢阅读,71,拓扑排序过程,AOV,网络,输出,V,3,后,2020-5-30,谢谢阅读,72,输出,V,4,后,输出,V,2,后,输出,V,1,后,输出,V,5,后,输出拓扑序列为：,3 4 2 1 5,2020-5-30,谢谢阅读,73,关键路径法,关键路径法是采用边表示活动,(Activity On Edge),的网络，简称为,AOE,网络。,AOE,网络是一个带权的有向无环路图，其中，每个顶点代表一个事件,(Event),，事件说明某些活动或某一项活动的完成，即阶段性的结果。,离开某顶点的各条边所代表的活动，只有在该顶点对应的事件出现后才能开始。,权值表示活动持续的时间。,2020-5-30,谢谢阅读,74,一个,AOE,网络,2020-5-30,谢谢阅读,75,AOE,网络,通常利用,AOE,网络可以研究以下两个问题：,(1),完成整个工程至少需要多少时间？,(2),哪些活动是影响工程进度的关键？,2020-5-30,谢谢阅读,76,关键路径,完成工程所需的时间就是从开始点起进行到结束点止所需的时间。,路径长度是指沿路径各边的权值之和，也就是这些边所代表的活动所需时间之和。,完成整个工程所需的时间取决于从开始点到结束点的最长路径长度，此长度最大的路径叫做,关键路径,。,分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的效率，缩短整个工期。,2020-5-30,谢谢阅读,77,求关键路径的算法描述,在描述关键路径的算法时，设活动,a,i,由弧,表示，要确定如下几个相关的量：,(1),事件,V,j,的,最早出现时间,和活动的,最早开始时间,：从源点,V,1,到某顶点,V,j,的最长路径长度叫作事件,j,的最早出现时间，表示成,vej,。顶点,V,j,的最早出现时间,vej,决定了从,V,j,指出的各条边所代表活动的最早开始时间，因为事件,j,不出现，它后面的各项活动就不能开始。我们以,ei,表示活动,a,i,的最早开始时间。显然,ei= vej,。,2020-5-30,谢谢阅读,78,求关键路径的算法描述,(,续,),(2),活动,a,i,的,最迟开始时间,：在不影响整个工程按时完成的前提下，此项活动最迟的必须开始时间，表示成,Li,。,只要某活动,a,i,有,Li=ei,的关系，我们就称,a,i,为,关键活动,。关键活动只允许在一个确定的时间开始，再早，它前面的事件还没出现，尚不能开始；再晚，又会延误整个工程的按时完成。由于完成整个工程所需的时间是由关键路径上各边权值之和所决定的，显然关键路径上各条边所对应的活动都是关键活动。,2020-5-30,谢谢阅读,79,求关键路径的算法描述,(,续,),(3),事件,j,的,最迟出现时间,：即事件,j,在不延误整个工程的前提下允许发生的最迟时间，表示为,vlj,。对某条指向顶点,V,k,的边所代表的活动,a,i,可得到：,Li= vlk-(,活动,a,i,所需时间,),也就是活动,a,i,必须先于它后面事件的最迟出现时间开始，提前的时间为进行此活动所需的时间。,下图所示为活动开始时间与事件出现时间的关系。,V,j,a,i,V,k,2020-5-30,谢谢阅读,80,求关键路径的算法描述,(,续,),确定关键路径的方法就是要确定,ei=Li,的关键活动。,假设以,wj,k,表示有向边,的权，即此边对应的活动所需的时间，为了求,AOE,网络中活动,a,i,的最早开始时间,ei,和活动,a,i,的最迟开始时间,Li,，先要求得顶点,V,k,的最早出现时间,vek,和最迟出现时间,vlk,。,2020-5-30,谢谢阅读,81,vek,和,vlk,可以采用下面的递推公式计算：,(1),向汇点递推,由源点的,ve1=0,开始，利用公式：,向汇点的方向递推，可逐个求出各顶点的,ve,。式中,p,表示所有指向顶点的边的集合。,2020-5-30,谢谢阅读,82,集合,p,此式的意义为：从指向顶点,V,k,的各边的活动中取最晚完成的一个活动的完成时间作为,V,k,的最早出现时间,vek,。,2020-5-30,谢谢阅读,83,(2),向源点递推,由上一步的递推，最后总可求出汇点的最早出现时间,ven,。因汇点就是结束点，最迟出现时间与最早出现时间相同，即,vln=ven,。从汇点的最迟出现时间,vln,开始，利用下面公式：,向源点的方向往回递推，可逐个求出各顶点的最迟出现时间,vl,。式中,s,表示所有由,V,j,点指出的边的集合，如下页图所示。,2020-5-30,谢谢阅读,84,集合,s,上述公式的意义为：由从,V,j,顶点指出的各边所代表的活动中取需最早开始的一个开始时间作为,V,j,的最迟出现时间,。,2020-5-30,谢谢阅读,85,无论是向汇点递推还是向源点递推，都必须按一定的顶点顺序进行。,对所有的有向边，向汇点递推是先求出尾顶点的,ve,值，再求头顶点的,ve,值；向源点递推则相反，先求头顶点的,vl,值，再求尾顶点的,vl,值。,为此，可利用上节介绍的拓扑排序得到的顶点次序进行向汇点的递推，向源点的递推按相反的顺序进行即可，不必再重新排序。,2020-5-30,谢谢阅读,86,AOE,网络中的关键活动,2020-5-30,谢谢阅读,87,求关键路径的算法描述,(,续,),由表可知时间余量为零的活动都是关键活动，即为,a,1,，,a,4,，,a,7,，,a,8,，,a,10,，,a,11,。,这些关键活动构成两条关键路径，即关键路径,(V,1,，,V,2,，,V,5,，,V,7,，,V,9,),和,(V,1,，,V,2,，,V,5,，,V,8,，,V,9,),。,在安排工程时，对于关键活动和余量小的活动应重点保证，余量较大的活动可适当地放松些，对非关键活动加速进行，并不能使整个工程提前完成，只有提高关键路径上的活动的效率，才能缩短整个工程的工期。,2020-5-30,谢谢阅读,88,7.6,最短路径,所谓,最短路径,（,shortest path,）问题指的是：如果从图中某顶点出发（此点称为源点），经图的边到达另一顶点（称为终点）的路径不止一条，如何找到一条路径使沿此路径上各边的权值之和为最小。,设一有向网络,G =,（,V,E,），已知各边的权值，并设每边的权均大于零，以某指定,V,0,为源点，求从,V,0,到图的其余各点的最短路径。,以下页图为例，若指定以顶点,V,6,为源点,V,0,，该图比较简单，通过观察可得到从,V,6,到其余各点的最短路径。,2020-5-30,谢谢阅读,89,最短路径例子,2020-5-30,谢谢阅读,90,狄杰斯特拉算法,狄克斯特拉于,1959,年提出了一个按路径“长度”递增的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法。,假设我们以邻接矩阵,cost,表示所研究的有向图，,costij,表示有向边,对应权值，如果两点之间无相应方向的边，则该元素取为无穷大。在计算机中此矩阵用一个（,nn,）二维数组表示（,n,为图的顶点数），无穷大元素则可用某很大的有限值（如,32767,）代替。,2020-5-30,谢谢阅读,91,有向图对应的邻接矩阵,2020-5-30,谢谢阅读,92,狄克斯特拉算法,狄克斯特拉算法需要一个顶点集合，初始时集合内只有一个源点,V,0,，以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程就结束了。,集合可用一维数组来表示，设此数组为,S,，凡在集合,S,以外的顶点，其相应的数组元素,Si,为,0,，否则为,1,。,还需要另一个一维数组,dist,，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为,disti=cost0i,，,i=2,n,。数组,dist,中的数据随着算法的逐步进行要不断地修改。,2020-5-30,谢谢阅读,93,定义了,S,集合和,dist,数组并对其初始化后，狄克斯特拉算法在进行中，都是从,S,之外的顶点集合中选出一个顶点,w,，使,distw,的值最小。于是从源点到达,w,只通过,S,中的顶点，把,w,加入集合,S,中，并调整,dist,中记录的从源点到集合中每个顶点,v,的距离：从原来的,distv,和,distw+costwv,中，选择较小的值作为新的,distv,。,重复上述过程，直到,S,中包含,V,中其余各顶点的最短路径。,2020-5-30,谢谢阅读,94,狄克斯特拉算法例子,以图所示的图为例来说明当指定以,V,6,为源点,V,0,后，用狄克斯特拉算法求最短路径的动态执行情况，其表示集合的数组,S,和表示距离的数组,dist,元素值的变化如图所示。,2020-5-30,谢谢阅读,95,算法动态执行情况,2020-5-30,谢谢阅读,96,2020-5-30,谢谢阅读,97,小 结,图,图的存储结构,邻接矩阵,邻接表,图的遍历,深度优先搜索,广度优先搜索,图的应用,最小生成树,最短路径问题,利用,AOV,网络研究拓扑排序问题,利用,AOE,网络研究关键路径的方法,2020-5-30,谢谢阅读,98,图的应用实例,在地理信息系统中的应用,在“变电站故障定位及恢复处理智能系统”中的应用,在,Internet,路由器中的应用,见：陈向群,.,数据结构,.,北京：人民邮电出版社，,2001,：,174-182.,2020-5-30,谢谢阅读,99,思考题,1.,用深度悠闲搜索和广度悠闲搜索对下图进行遍历,(,从顶点,1,出发,),给出遍历序列,.,1,2,3,6,4,5,7,8,2020-5-30,谢谢阅读,100,2020-5-30,谢谢阅读,101,思考题,2.,对下列所示的无向带权图，,(1),写出它的邻接矩阵，并按普里姆算法求其最小生成树；,(2),写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。,a,b,c,d,e,f,g,h,4,9,3,2,6,5,3,5,5,5,7,6,5,4,2020-5-30,谢谢阅读,102,