数据结构第07章图.ppt

第七章图,本章介绍另一种非线性数据结构图图：是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继；,第七章图7.1图的概念7.2图的存储结构7.3图的遍历7.4生成树7.5最短路径7.6拓扑排序,第七章图,学习要点1熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系；2熟练掌握图的两种遍历：深度优先遍历和广度优先遍历的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略3理解各种图的算法；,第七章图,7.1图的基本概念,一图的概念图的定义图G由两个集合构成，记作G=其中V是顶点的非空有限集合，E是边的有限集合，其中边是顶点的无序对或有序对集合。,G1=V=v0,v1,v2,v3,v4E=(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4),G1图示,无序对(vi,vj)：用连接顶点vi、vj的线段表示，称为无向边；,例,G2图示,有序对：用以vi起点、以vj为终点的有向线段表示，称为有向边或弧；称vi为弧尾，vj为弧头,无向图：在图G中，若所有边是无向边，则称G为无向图；有向图：在图G中，若所有边是有向边，则称G为有向图；混和图：在图G中，既有无向边也有有向边，则称G为混合图；,7.1图的基本概念,G2=V=v0v1,v2,v3E=,图的应用举例例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系,7.1图的基本概念,1邻接点及关联边邻接点：边的两个顶点,v、u互为邻接点关联边：若边e=(v,u),则称顶点v、u关联边e2顶点的度、入度、出度在无向图中：顶点V的度=与V相关联的边的数目在有向图中：顶点V的出度=以V为起点有向边数顶点V的入度=以V为终点有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n，边数为e图的所有顶点的度数和=2*e（每条边对图的所有顶点的度数和“贡献”2度）,e,图的基本术语,7.1图的基本概念,完全图、权、网有向完全图具有n(n-1)条弧的n个顶点的有向图称为无向完全图有n(n-1)/2条边的n个顶点的无向图称为权与图的边或弧相关的数叫网带权的图叫,7.1图的基本概念,4路径、回路路径路径是顶点的序列V=Vi0,Vi1,Vin，满足(Vij-1,Vij)E或E,(1arcsjiw;,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。,邻接矩阵法优点：,邻接矩阵法缺点：,注：用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX/最大值#defineMAX_VERTEX_NUM20/假设的最大顶点数typedefenumDG,DN,AG,ANGraphKind;/有向/无向图，有向/无向网typedefstructArcCell/弧（边）结点的定义VRTypeadj;/顶点间关系，无权图取1或0；有权图取权值类型InfoType*info;/该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstruct/图的定义VertexTypevexsMAX_VERTEX_NUM;/顶点表，用一维向量即可AdjMatrixarcs;/邻接矩阵intVernum,arcnum;/顶点总数，弧（边）总数GraphKindkind;/图的种类标志Mgraph;,图的邻接矩阵存储表示（参见教材P161）,对于n个顶点的图或网，空间效率=O(n2),StatusCreateUDN(Mgraph/CreateUDN,例：用邻接矩阵生成无向网的算法（参见教材P162）,对于n个顶点e条弧的网，建网时间效率=O(n2+n+e*n),邻接表(AdjacencyList),在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边。每个结点由三个域组成：,邻接点域,指示与顶点vi邻接的点在图中的位置,链域,指示下一条边或弧的结点,数据域,存储与边或弧相关的信息，如权值，无权图一般不用,每个单链表附设一个头结点。在表头结点中，除了设有链域指向链表中第一个结点之外，还设有存储顶点vi的名或其它有关信息的数据域。,数据域,链域,表头结点可以链相接，通常以顺序结构的形式存储，以便随机访问任一顶点的链表。,存放与该顶点相关的信息,指示第一条依附于该顶点的边的指针,图的邻接表存储表示,#defineMAX_VERTEX_NUM20typedefstructArcNodeintadjvex;/该弧所指向的顶点的位置structArcNode*nextarc;/指向下一条弧的指针InfoType*info;/该弧相关信息的指针ArcNode;typedefstructVNodeVertexTypedata;/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧VNode,AdjListMAX_VERTEX_NUM;typedefstructAdjListvertices;intvexnum,arcnum;/图的当前顶点数和弧数intkind;/图的种类标志ALGraph;,无向图的邻接表,在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数。,有向图的邻接表(出边表),有向图中对每个结点建立以Vi为尾的弧的单链表顶点：用一维数组存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储,有向图的逆邻接表(入边表),有向图中对每个结点建立以Vi为头的弧的单链表顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储,在有向图中，第i个链表中的结点个数只是顶点vi的出度，为求入度，必须遍历整个邻接表。在所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。在有向图的邻接表中，第i个边链表链接的边都是顶点i发出的边。也叫做出边表。在有向图的逆邻接表中，第i个边链表链接的边都是进入顶点i的边。也叫做入边表。,该结点表示边（ViVj）,其中的2是Vj在一维数组中的位置,邻接表,特点无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数判定两顶点v,u是否邻接：要看v对应线性链表中有无对应的结点u在G中增减边：要在两个单链表插入、删除结点；若无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。可见，G占用存储空间与G的顶点数、边数均有关；适用于边稀疏的图。,带权图的邻接表,多一个info域,相反，已知某网的邻接（出边）表，可以画出该网络。,80,64,1,2,5,当邻接表的存储结构形成后，图便唯一确定！,邻接表的缺点：,邻接表的优点：,空间效率高；容易寻找顶点的邻接点；,判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。,讨论：邻接表与邻接矩阵有什么异同之处？,1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（en2),三、十字链表（自学）（适用于有向图）四、邻接多重表（自学）（适用于无向图）,有向图的十字链表表示法,无向图的邻接多重表表示法,7.3图的遍历,从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次。这一过程就称为图的遍历。图的遍历比树的遍历要复杂得多。因为图的任一顶点都可能和其余的顶点相邻接；因此在访问了某个顶点后，可能沿着某条路径搜索后，又回到该顶点上。为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。,为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组visited0.n-1，它的初始状态为0，在图的遍历过程中，一旦某一个顶点i被访问，就立即让visitedi为1，防止它被多次访问。,通常有两条遍历图的路径：深度优先搜索、广度优先搜索,深度优先搜索DFS(Depth_FirstSearch),算法思想：假设初始状态是图中所有顶点未曾被访问，则可从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,图的深度优先搜索类似于树的前序遍历,深度优先搜索的示例,由上得到顶点访问序列为：v1、v2、v4、v8、v5、v3、v6、v7,显然这是一个递归的过程，为了在遍历过程中便于区分顶点是否已被访问，需附设访问数组visited0.n-1，数组元素的初始值为false；在遍历过程中，一旦某一个顶点i被访问，则置visitedi为true。,例2：,v2v1v3v5,DFS结果,v4v6,起点,深度优先搜索（遍历）步骤：,详细归纳：在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还未被访问过的顶点w2；然后再从w2出发，进行类似的访问，如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。,简单归纳：访问起始点v;若v的第1个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找v的第2个邻接点重新遍历。,接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。,BooleanvisitedMAX;/访问标志数组Status(*VisitFunc)(intv);/函数变量/以上两个变量都是全局变量voidDFSTraverse(GraphG,Status(*Visit)(intv)/对图G作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用DFS,图的深度优先搜索算法,voidDFS(GraphG,intv)/从第v个顶点出发递归地深度优先遍历图G。visitedv=TRUE;/访问标记置为trueVisitFunc(v);/访问第v个顶点for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w/递归调用DFS,算法时间复杂度分析,从上述算法可知，在遍历过程中，对图中每个顶点至多调用一次DFS函数；因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，对图的遍历实际上是对每个顶点查找其邻接点的过程，耗费的时间取决于所用的存储结构。,如果用邻接表表示图，沿Firstoutlink链可以找到某个顶点v的所有邻接顶点w。由于总共有2e个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。,广度优先搜索BFS(Breadth_FirstSearch),图的广度优先搜索类似于树的按层次遍历过程,算法思想：从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,广度优先搜索的示例,由上得到顶点访问序列为：v1、v2、v3、v4、v5、v6、v7、v8,为了实现对图的逐层访问，需要在算法中使用一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。为避免重复访问，还需要一个辅助数组visited0.n-1，给被访问过的顶点加标记。,例2：,v3,BFS结果,v4v5,v2v1v6,v9v8v7,起点,广度优先搜索（遍历）步骤：,简单归纳：在访问了起始点v之后，依次访问v的邻接点；然后再依次访问这些顶点中未被访问过的邻接点；直到所有顶点都被访问过为止。,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,图的广度优先搜索算法,voidBFSTraverse(GraphG,Status(*Visit)(intv)/按广度优先非递归遍历图G。/使用辅助队列Q和访问标志数组visited。for(v=0;vG.vexnum;+v)visitedv=FALSE;InitQueue(Q);/置空的辅助队列Qfor(v=0;vG.vexnum;+v)if(!visitedv)/若顶点v尚未被访问EnQueue(Q,v);/顶点v入队列while(!QueueEmpty(Q)DeQueue(Q,u);/队头元素出队并置为uvisitedu=TRUE;Visit(u);/访问u,for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w)if(!visitedw)/u的尚未访问的邻接点w入队visitedw=TRUE;Visit(w);/访问wEnQueue(Q,w);/if/while/if/BFSTraverse,如果使用邻接表表示图，则循环的总时间代价为d0+d1+dn-1=O(e)，其中的di是顶点i的度。如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的n个元素，总的时间代价为O(n2)。,算法时间复杂度分析,7.4图的连通性,当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图(连通分量)的所有顶点。若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。,例,图G4,G4的三个连通分量,在以上算法中，需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。,对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。,最小生成树(minimumcostspanningtree),使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。,假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。问题是：如何在最节省经费的前提下建立这个通信网。,解决办法：在每两个城市之间设置一条线路，n个城市之间最多可设置n(n-1)/2条线路；要在这些可能的线路中选择n-1条，以使总的耗费最少。,可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋予边的权值表示相应的代价。,对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。从这些生成棵中选择权值最小的，就满足建立耗费最小的通信网的要求了。这个问题就是构造连通网的最小代价生成树问题，简称为最小生成树问题。,构造最小生成树的准则,1、必须只使用该网络中的边来构造最小生成树；2、必须使用且仅使用n-1条边来联结网络中的n个顶点；3、不能使用产生回路的边。,构造最小生成树可以有多种算法，大多数算法都利用了以下MST性质：假设N=(V,E)是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中uU,vV-U，则必存在一棵包含边(u,v)的最小生成树。,普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两个利用以上MST性质构造最小生成树的算法。,普里姆算法(Prim),可取图中任意一个顶点v作为生成树的根，之后若要往生成树上添加顶点w，则在顶点v和顶点w之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。一般情况下，假设n个顶点分成两个集合：U（包含已落在生成树上的结点）和V-U（尚未落在生成树上的顶点），则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,普里姆算法的基本思想：从连通网络N=V,E中的某一顶点u0出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。,为了实现以上算法，还需要附设一个辅助数组closedge0.n-1，以记录从U到V-U具有最小代价的边。,structVertexTypeadjvex;/存储该边依附的在U中的顶点VRTypelowcost;/存储该边上的权closedgeMAX_VERTEX_NUM;,普里姆算法构造最小生成树的过程,起点,7,13,9,5,10,起点,例,算法时间复杂度分析,从上述算法可知，若网中有n个顶点，则第一次进行初始化的循环语句的频度为n，第二次循环语句包含两个内循环：一是在closedgev.lowcost中求最小值，其频度为n-1；二是重新选择具有最小代价的边,其频度为n。由此可知，普里姆算法的时间复杂度为O(n2),与网中的边数无关，适用于求边稠密的网的最小生成树。,克鲁斯卡尔算法(Kruskal),为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。克鲁斯卡尔算法的做法就是：先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。,算法的基本思想：设有一个有n个顶点的连通网络N=V,E,最初先构造一个只有n个顶点，没有边的非连通图T=V,图中每个顶点自成一个连通分量。当在E中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到T中；否则将此边舍去，重新选择一条权值代价最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。,克鲁斯卡算法构造最小生成树的过程,7,13,9,5,10,例,算法时间复杂度分析,上述算法至多对e条边各扫描一次，假若以“堆”来存储网中的边，则每次选择最小代价的边仅需O(loge)的时间。而且生成树T的每个连通分量可看成是一个等价类，则构造T加入新的边的过程类似于求等价类的过程，则可用MFSet类型来描述T，使构造T的过程仅需O(eloge)的时间。因此，克鲁斯卡尔算法的时间复杂度为O(n2)，适用于求边稀疏的网的最小生成树。,7.5有向无环图及其应用,一个无环的有向图称做有向无环图，简称DAG图。有向无环图是描述含有公共子式的表达式的有效工具。,如：表达式(a+b)*(b*(c+d)+(c+d)*e)(c+d)*e)中，对于一些相同的子表达式如(c+d)、(c+d)*e，可以利用有向无环图，实现对相同子式的共享，从而节省存储空间。,有向无环图也是描述一项工程或系统的进行过程的有效工具。,通常把工程分成若干个称作活动的子工程，而这些子工程之间通常受着一定条件的约束,如其中某些子工程的开始必须在另一些子工程完成之后。对整个工程和系统，主要考虑以下两个问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间。对应于有向图，即为进行拓扑排序和关键路径的操作。,拓扑排序,例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。,C1高等数学C2程序设计基础C3离散数学C1,C2C4数据结构C3,C2C5高级语言程序设计C2C6编译方法C5,C4C7操作系统C4,C9C8普通物理C1C9计算机原理C8,课程代号,课程名称,先修课程,表示课程之间优先关系的有向图,由上可知，可用有向图表示一个工程。,在这种有向图中，用顶点表示活动，用有向边表示活动。Vi必须先于活动Vj进行。这种有向图叫做顶点表示活动的AOV网络(ActivityOnVertices)。,因此，对给定的AOV网络，必须先判断它是否存在有向环。,在AOV网络中，如果活动Vi必须在活动Vj之前进行，则存在有向边，AOV网络中不能出现有向回路，即有向环。在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,进行拓扑排序的方法,1、在AOV网络中选一个没有直接前驱的顶点，并输出之;2、从图中删去该顶点，以及所有以它为尾的弧;3、重复以上两步,直到1）全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；2）图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。,拓扑排序过程的示例,(h)全部结点已输出，拓扑排序完成,由上得到的拓扑有序序列为C4,C0,C3,C2,C1,C5。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。,拓扑排序的算法实现,可以用邻接表作有向图的存储结构，且在头结点中增加一个存放顶点入度的数组(indegree)。入度为0的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，可用弧头顶点的入度减1的方法来实现。,另外，使用一个存放入度为零的顶点的链式栈，供选择和输出无前驱的顶点。只要出现入度为零的顶点，就将它加入栈中。,(1)建立入度为零的顶点栈;(2)当入度为零的顶点栈不空时,重复执行：从顶点栈中退出一个顶点,并输出之;从AOV网络中删去这个顶点和它发出的边,边的终顶点入度减一;如果边的终顶点入度减至0,则该顶点进入度为零的顶点栈;(3)如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存在有向环。,使用这种栈的拓扑排序算法可以描述如下：,拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,一个AOV网的拓扑序列不是唯一的,算法实现以邻接表作存储结构把邻接表中所有入度为0的顶点进栈栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕,邻接表结点：typedefstructnodeintvex;/顶点域structnode*next;/链域JD;,表头结点：typedefstructtnodeintin;/入度域structnode*link;/链域TD;TDgM;/g0不用,算法分析,建邻接表：T(n)=O(e)搜索入度为0的顶点的时间：T(n)=O(n)拓扑排序：T(n)=O(n+e),Ch6_4.c,算法描述,Ch6_40.c,1,6,输出序列：6,输出序列：6,输出序列：6,输出序列：6,输出序列：6,输出序列：6,输出序列：61,输出序列：61,输出序列：61,4,输出序列：61,4,输出序列：61,4,输出序列：61,4,3,输出序列：61,4,3,输出序列：61,4,3,输出序列：61,4,3,输出序列：61,4,3,输出序列：613,4,3,输出序列：613,4,输出序列：613,4,输出序列：613,4,输出序列：613,4,2,输出序列：613,4,2,输出序列：613,4,2,输出序列：6132,4,2,输出序列：6132,4,输出序列：61324,4,输出序列：61324,输出序列：61324,5,输出序列：61324,5,输出序列：613245,5,输出序列：613245,分析此拓扑排序算法可知，如果AOV网络有n个顶点，e条边，在拓扑排序的过程中，搜索入度为零的顶点，建立链式栈所需要的时间是O(n)。在正常的情况下，有向图有n个顶点，每个顶点进一次栈，出一次栈，共输出n次。顶点入度减一的运算共执行了e次。所以总的时间复杂度为O(n+e)。,算法时间复杂度分析,关键路径,如果在带权有向无环图中用有向边表示一个工程中的活动(Activity)用边上权值表示活动持续时间(Duration)用顶点表示事件(Event)则这样的有向图叫做用边表示活动的网络，简称AOE(ActivityOnEdges)网络。,一个AOE网络,AOE网络在某些工程估算方面非常有用，可以使人们了解：(1)完成整个工程至少需要多少时间(假设网络中没有环)?(2)为缩短完成工程所需的时间,应当加快哪些活动?,在AOE网络中,有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条；这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。,因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(CriticalPath)。,要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。,关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径。,几个与计算关键活动有关的量：,事件Vi的最早可能开始时间Ve(i)是从源点V0到顶点Vi的最长路径长度。事件Vi的最迟允许开始时间Vli是在保证汇点Vn-1在Ven-1时刻完成的前提下，事件Vi的允许的最迟开始时间。,活动ak的最早可能开始时间ek设活动ak在边上，则ek是从源点V0到顶点Vi的最长路径长度。因此,ek=Vei。活动ak的最迟允许开始时间lklk是在不会引起时间延误的前提下，该活动允许的最迟开始时间。lk=Vlj-dur()。其中，dur()是完成ak所需的时间。时间余量lk-ek表示活动ak的最早可能开始时间和最迟允许开始时间的时间余量。lk=ek表示活动ak是没有时间余量的关键活动。,为找出关键活动,需要求各个活动的ek与lk，以判别是否lk=ek。为求得ek与lk，需要先求得从源点V0到各个顶点Vi的各事件的最早开始时间Vei和最迟开始时间Vli。,求最早开始时间Vej和最迟开始时间Vlj需分两步进行：,（1）从Ve0=0开始，向前递推,T,i=1,2,n-1,其中,T是所有以第j个顶点为头的弧的集合。,(2)从Vln-1=Ven-1开始，反向递推,S,i=n-2,n-3,0,其中,S是所有以第i个顶点为尾的弧的集合。,以上这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。,*设活动ak(k=1,2,e)在带权有向边上,它的持续时间用dut()表示，则有ek=Vei；lk=Vlj-dur()；k=1,2,e。这样就得到计算关键路径的算法。*计算关键路径时，可以一边进行拓扑排序一边计算各顶点的Vei。为了简化算法，假定在求关键路径之前已经对各顶点实现了拓扑排序，并按拓扑有序的顺序对各顶点重新进行了编号。算法在求Vei,i=0,1,n-1时按拓扑有序的顺序计算，在求Vli,i=n-1,n-2,0时按逆拓扑有序的顺序计算。,（1）输入e条弧，建立AOV-网的存储结构；（2）从源点v1出发，令ve1=0，按拓扑有序求其余各顶点的最早发生时间vei（2=i=n）。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤（3）。,求关键路径的过程：,（3）从汇点vn出发，令vln=ven，按逆拓扑有序号求其余各顶点的最迟发生时间vli（n-1i1）；（4）根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。,求关键路径的示例,在拓扑排序求Vei和逆拓扑有序求Vli时,所需时间为O(n+e),求各个活动的ek和lk时所需时间为O(e),总共花费时间仍然是O(n+e)。,算法时间复杂度分析,求关键路径步骤求Ve(i)求Vl(j)求e(i)求l(i)计算l(i)-e(i),V1V2V3V4V5V6V7V8V9,064577161418,0668710161418,a1a2a3a4a5a6a7a8a9a10a11,0,0,0,0,2,2,6,6,0,4,6,2,5,8,3,7,7,0,7,7,0,7,10,3,16,16,0,14,14,0,0,3,3,算法实现以邻接表作存储结构从源点V1出发，令Ve1=0,按拓扑序列求各顶点的Vei从汇点Vn出发，令Vln=Ven,按逆拓扑序列求其余各顶点的Vli根据各顶点的Ve和Vl值，计算每条弧的ei和li,找出ei=li的关键活动,邻接表结点：typedefstructnodeintvex;/顶点域intlength;/权值structnode*next;/链域JD;,表头结点：typedefstructtnodeintvexdata;/顶点信息intin;/入度域structnode*link;/链域TD;TDgM;/g0不用,算法描述输入顶点和弧信息，建立其邻接表计算每个顶点的入度对其进行拓扑排序排序过程中求顶点的Vei将得到的拓扑序列进栈按逆拓扑序列求顶点的Vli计算每条弧的ei和li,找出ei=li的关键活动,Ch6_20.c,一顶点到其余各顶点,7.6.求最短路径,两种常见的最短路径问题：一、单源最短路径用Dijkstra（迪杰斯特拉）算法二、所有顶点间的最短路径用Floyd（弗洛伊德）算法,典型用途：交通问题。如：城市A到城市B有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何选择一条线路，使总费用（或总时间）最少？问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。,（注：最短路径与最小生成树不同，路径上不一定包含n个顶点）,任意两顶点之间,一、单源最短路径(Dijkstra算法),目的：设一有向图G=（V,E），已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于或等于0。,例1：,源点,从FA的路径有4条：FA：24FBA：518=23FBCA：5+7+9=21FDCA：25+12+9=36,又：从FB的最短路径是哪条？从FC的最短路径是哪条？,10,30,100,例2：,60,01234,50,90,70,讨论：计算机如何自动求出这些最短路径？,60,Dijkstra（迪杰斯特拉）算法,算法思想：先找出从源点v0到各终点vk的直达路径（v0,vk），即通过一条弧到达的路径。从这些路径中找出一条长度最短的路径（v0,u）,然后对其余各条路径进行适当调整：若在图中存在弧（u,vk），且（v0,u）+（u,vk）（v0,vk）,则以路径（v0,u,vk）代替（v0,vk）。在调整后的各条路径中，再找长度最短的路径，依此类推。,总之，按路径“长度”递增的次序来逐步产生最短路径,算法描述：,（1）设arcsnn为有向网的带权邻接矩阵，arcsij表示弧（vi，vj)的权值，S为已找到从源点v0出发的最短路径的终点集合，它的初始状态为v0.辅助数组Dn为各终点当前找到的最短路径的长度，它的初始值为Diarcsv0,i/即邻接矩阵中第v0行的权值,（2）选择u，使得DuminDw|wV-S/w是S集之外的顶点/Du是从源点v0到S集外所有顶点的弧中最短的一条S=Su/将u加入S集,（3）对于所有不在S中的终点w，若Du+arcsu,wDw/即(v0,u)(u,w)(v0,w)则修改Dw为：DwDu+arcsu,w,（4）重复操作（2）、（3）共n-1次，由此求得从v0到各终点的最短路径。,算法的C语言程序见教材P189；,对应流程图见下页,VoidShortPath_DIJ(MgraphG,intv0,PathMatrix+i),更新v0到V-S中顶点的dist,求最短路径长度,算法流程：,(v0,v2)+(v2,v3)(v0,v3),S之外的当前最短路径之顶点,v0,v2,v0,v2,v4,v0,v2,v4,v3,v0,v2,v4,v3,v5,例3：,v2,v4,v3,v5,012345,Dw,012345,与最小生成树的不同点：路径可能是累加的！,10v0,v2,50v0,v4,v3,30v0,v4,二、所有顶点之间的最短路径,问题的提出：已知一个各边权值均大于0的带权有向图，对每一对顶点vivj，希望求出vi与vj之间的最短路径和最短路径长度。解决思路：可以通过调用n次Dijkstra算法来完成，但时间复杂度为O(n3)。改进：Floyd算法（略）,图,存储结构,遍历,最小生成树,（利用DFS）,本章小结,(利用DFS和BFS),最短路径(ShortestPath),最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。问题解法边上权值非负情形的单源最短路径问题Dijkstra算法边上权值为任意值的单源最短路径问题Bellman和Ford算法所有顶点之间的最短路径Floyd算法,边上权值非负情形的单源最短路径问题,问题的提法：给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。限定各边上的权值大于或等于0。为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。举例说明,Dijkstra逐步求解的过程,引入一个辅助数组dist。它的每一个分量disti表示当前找到的从源点v0到终点vi的最短路径的长度。初始状态：若从源点v0到顶点vi有边，则disti为该边上的权值；若从源点v0到顶点vi没有边，则disti为+。一般情况下，假设S是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从v0出发，中间只经过S中的顶点便可到达的那些顶点vx(vxV-S)的路径中的一条。每次求得一条最短路径之后，其终点vk加入集合S，然后对所有的viV-S，修改其disti值。,Dijkstra算法可描述如下：,初始化：Sv0;distjEdge0j,j=1,2,n-1;/n为图中顶点个数求出最短路径的长度：distkmindisti,iV-S;SSUk;修改：distimindisti,distk+Edgeki,对于每一个iV-S;判断：若S=V,则算法结束，否则转。,Dijkstra算法中各辅助数组的变化,如何从表中读取源点0到终点v的最短路径？举顶点4为例path4=2path2=3path3=0，反过来排列，得到路径0,3,2,4，这就是源点0到终点4的最短路径。,0,4,1,2,3,10,50,10,20,60,30,100,边上权值为任意值的单源最短路径问题,带权有向图D的某几条边或所有边的长度可能为负值。利用Dijkstra算法，不一定能得到正确的结果。源点0到终点2的最短路径应是0,1,2，其长度为2，它小于算法中计算出来的dist2的值。,若设源点v=0，使用Dijkstra算法所得结果,0,1,1,5,7,-5,Bellman和Ford提出了从源点逐次绕过其它顶点，以缩短到达终点的最短路径长度的方法。该方法有一个限制条件，即要求图中不能包含有由带负权值的边组成的回路。当图中没有由带负权值的边组成的回路时，有n个顶点的图中任意两个顶点之间如果存在最短路径，此路径最多有n-1条边。我们将以此为依据考虑计算从源点v到其它顶点u的最短路径的长度distu。,0,1,2,5,7,-5,0,1,2,1,1,-2,Bellman-Ford方法构造一个最短路径长度数组序列dist1u，dist2u，distn-1u。其中，dist1u是从源点v到终点u的只经过一条边的最短路径的长度，dist1u=Edgevu；dist2u是从源点v最多经过两条边到达终点u的最短路径的长度，dist3u是从源点v出发最多经过不构成带负长度边回路的三条边到达终点u的最短路径的长度，distn-1u是从源点v出发最多经过不构成带负长度边回路的n-1条边到达终点u的最短路径的长度。算法的最终目的是计算出distn-1u。可以用递推方式计算distku。,dist1u=Edgevu；distku=mindistk-1u,mindistk-1j+Edgeju设已经求出distk-1j,j=0,1,n-1,此即从源点v最多经过不构成带负长度边回路的k-1条边到达终点j的最短路径的长度。从图的邻接矩阵中可以找到各个顶点j到达顶点u的距离Edgeju，计算mindistk-1j+Edgeju，可得从源点v绕过各个顶点，最多经过不构成带负长度边回路的k条边到达终点u的最短路径的长度。用它与distk-1u比较，取小者作为distku的值。,图的最短路径长度,所有顶点之间的最短路径,问题的提法：已知一个各边权值均大于0的带权有向图，对每一对顶点vivj，要求求出vi与vj之间的最短路径和最短路径长度。Floyd算法的基本思想：定义一个n阶方阵序列：A(-1),A(0),A(n-1).其中A(-1)ij=Edgeij；A(k)ij=minA(k-1)ij，A(k-1)ik+A(k-1)kj,k=0,1,n-1,A(0)ij是从顶点vi到vj,中间顶点是v0的最短路径的长度,A(k)ij是从顶点vi到vj,中间顶点的序号不大于k的最短路径的长度,A(n-1)ij是从顶点vi到vj的最短路径长度。,所有各对顶点之间的最短路径voidGraph:AllLengths(intn)/Edgenn是一个具有n个顶点的图的邻接矩阵。/aij是顶点i和j之间的最短路径长度。pathij/是相应路径上顶点j的前一顶点的顶点号,在求/最短路径时图的类定义中要修改path为/pathNumVerticesNumVertices。,for(inti=0;ij/缩短路径长度,绕过k到j,以Path(3)为例，对最短路径的读法加以说明。从A(3)知，顶点1到0的最短路径长度为a10=11,其最短路径看path10=2，path12=3，path13=1,表示顶点0顶点2顶点3顶点1;从顶点1到顶点0最短路径为,。Floyd算法允许图中有带负权值的边，但不许有包含带负权值的边组成的回路。本章给出的求解最短路径的算法不仅适用于带权有向图，对带权无向图也可以适用。因为带权无向图可以看作是有往返二重边的有向图，只要在顶点vi与vj之间存在无向边(vi,vj)，就可以看成是在这两个顶点之间存在权值相同的两条有向边和。,6.7最短路径问题提出,用带权的有向图表示一个交通运输网，图中：顶点表示城市边表示城市间的交通联系权表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图