数据结构第7章图.ppt

第七章 图 图状结构是一种比树形结构更复杂的非线性结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中数据元素之间有着明显的层次关系，并且每一层的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。,7.1 图的定义和术语 一、图的定义： 图（Graph）是由非空的顶点集合和一个描述顶点之间关系（边或者弧）的集合组成，其二元组定义为： G（V，E） Vvi| vidataobject E（ vi,vj）| vi, vj VP（vi, vj） 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中P（vi,vj）表示顶点vi和顶点vj之间有一条直接连线。集合E可以是空集，若E为空，则该图只有顶点而没有边。偶对（vi,vj）表示一条边。,二、图的基本术语 有向图和无向图 在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。如图所示，G1为无向图，G2为有向图。 在无向图中，一条边（x,y）与（y,x）表示的结果相同，用圆括号表示，在有向图中，一条边与表示的结果不相同，故用尖括号表示。表示从顶点x出发向顶点y的边，x为始点，y为终点。有向边也称为弧，x为弧尾，y为弧头,则表示为一条弧,而表示y为弧尾、x为弧头的另一条弧 。,2,4,5,1,3,6,G1,图G1中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , ,1,5,7,3,2,4,G2,6,图G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7),完全图、稠密图、稀疏图 具有n个顶点，n(n-1)/2条边的图，称为无向完全图，具有n个顶点，n(n-1) 条弧的有向图,称为有向完全图。无向完全图和有向完全图都称为完全图。 当一个图接近完全图时，则称它为稠密图，相反地，当一个图中含有较少的边或弧时，则称它为稀疏图。,有向完全图,无向完全图,3. 度、入度、出度 在图中，一个顶点依附的边或弧的数目，称为该顶点的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，有向图中某个顶点的入度和出度之和称为该顶点的度。 另外，若图中有n个顶点，e条边或弧，第i个顶点的度为di，则有e=,2,4,5,1,3,6,G2,顶点2入度：1 出度：3 顶点4入度：1 出度：0,G1,顶点5的度：3 顶点2的度：4,子 图 若有两个图G1和G2， G1=(V1,E1)， G2=(V2,E2)， 满足如下条件： V2V1 ，E2 E1，即V2为V1的子集，E2为E1的子集，称图G2为图G1的子图。,5 权 在图的边或弧中给出相关的数，称为权。 权可以代表一个顶点到另一个顶点的距离，耗费等，带权图一般称为网。,6 连通图和强连通图 在无向图中，若从顶点i到顶点j有路径，则称顶点i和顶点j是连通的。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图。 在有向图中，若从顶点i到顶点j有路径，则称从顶点i和顶点j是连通的，若图中任意两个顶点都是连通的，则称此有向图为强连通图，否则称为非强连通图。,7 连通分量和强连通分量 无向图中，极大的连通子图为该图的连通分量。显然，任何连通图的连通分量只有一个，即它本身，而非连通图有多个连通分量。 有向图中，极大的强连通子图为该图的强连通分量。显然，任何强连通图的强连通分量只有一个，即它本身，而非强连通图有多个强连通分量。,8路径、回路 在无向图G中，若存在一个顶点序列Vp ,Vi1，Vi2，Vin，Vq, 使得（Vp,Vi1）,(Vi1,Vi2),，(Vin,Vq)均属于E（G），则称顶点Vp到Vq存在一条路径。若一条路径上顶点均不相同，则称此路径为简单路径。起点和终点相同的路径称为回路，简单路径组成的回路称为简单回路。路径上经过的边的数目称为该路径的路径长度。 9 生成树、生成森林 连通图的生成树是一个极小连通子图，它包含图中全部n个顶点和n-1条不构成回路的边。非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。,1,5,7,3,2,4,G2,6,2,4,5,1,3,6,G1,路径：1，2，3，5，6，3 路径长度：5 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3,路径：1，2，5，7，6，5，2，3 路径长度：7 简单路径：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 简单回路：1，2，3，1,三、基本操作： 1Creatgraph（g）输入图的顶点和边，建立图G的存储。 2Destroygraph（g）释放图占用的存储空间。 3Getvertex（g，vi）在图中找到顶点vi，并返回顶点vi 的相关信息。 4Addvertex（g，vi）在图中增添新顶点vi。 5Delvertex（g，vi）在图中，删除顶点vi以及所有和顶点 vi相关联的边或弧。 6AddArc（g，vi，vj）在图中增添一条从顶点vi到顶点vj 的边或弧。 7DelArc（g，vi，vj）在图中删除一条从顶点vi到顶点vj 的边或弧。 8DFS（g，vi）在图中，从顶点vi出发深度优先遍历图。 9BFS（g，vi）在图中，从顶点vi出发广度优先遍历图。,7.2 图的存储表示 图是一种结构复杂的数据结构，表现在不仅各个顶点的度可以千差万别，而且顶点之间的逻辑关系也错综复杂。从图的定义可知，一个图的信息包括两部分，即图中顶点的信息以及描述顶点之间的关系（边或者弧）的信息。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方面的信息。 图通常有邻接矩阵、邻接表、邻接多重表和十字链表等表示方法。,一、数组表示法（邻接矩阵） 1. 定义 在邻接矩阵表示中，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。若（i,j）E(G)或i,jE(G),则矩阵中第i 行 第j 列元素值为1，否则为0 。,从无向图的邻接矩阵可以得出如下结论： （1）矩阵是对称的; （2）第i行或第i 列1的个数为顶点i 的度; （3）矩阵中1的个数的一半为图中边的数目; （4）很容易判断顶点i 和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。 从有向图的邻接矩阵可以得出如下结论： （1） 矩阵不一定是对称的; （2） 第i 行中1的个数为顶点i 的出度; （3） 第i列中1的个数为顶点 i的入度; （4） 矩阵中1的个数为图中弧的数目; （5） 很容易判断顶点i 和顶点j 是否有弧相连.,网的邻接矩阵表示 如果图的各边是带权的，只需将矩阵中的各个1元素换成相应边的权即可。,2. 图的邻接矩阵数据类型描述 在用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外还有图的顶点数和边数。故可将其形式描述如下： #define MaxVertex 30 typedef struct char vexsMaxVertex; int edgesMaxVertexMaxVextex; int n,e; Mgraph; 3. 邻接矩阵建立算法(见课本P125-P126）,二、邻接表 邻接表（Adjacency List）是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有点的邻接表表头放到数组中，就构成了图的邻接表。其中，单链表中的结点称为表结点，每个单链表设的一个头结点称为顶点结点。,无向图邻接表 对图中每个顶点Vi建立一个单链表，链表中的结点表示依附于顶点vi的边，每个链表结点为两个域： 其中：邻接点域（adjvex）记载与顶点Vi邻接的顶点信息； 链域（nextarc）指向下一个与顶点Vi邻接的结点 每个链表附设一个头结点，头结点结构为： 其中：vexdata存放顶点信息（姓名、编号等）； firstarc指向链表的第一个结点。,2,5,3,4,5,1,2,2,1 2 3 4 5,特点：设无向图中顶点数为n，边数为e， 则它的邻接表需要n个头结点和2e个表结点。 顶点Vi的度 TD（Vi）=链表i中的表结点数。,有向图邻接表 与无向图的邻接表结构一样。只是在第i条链表上的结点是以vi为弧尾的各个弧头顶点,2,3,4,2,1 2 3 4,特点： 1. n个顶点，e条弧的有向图，需n个表头结点，e 个表结点 2. 第i条链表上的结点数，为Vi的出度 （求顶点的出度易，求入度难）,有向图逆邻接表 从有向图的邻接表可知，很难求出顶点的入度。为此，必须另外建立有向图的逆邻接表，以便求出每一个顶点的入度。与无向图的邻接表结构一样。只是在第i条链表上的结点是以vi为弧头的各个弧尾顶点。,2,3,4,1 2 3 4,此时，第i条链表上的结点数，为Vi的入度,4. 结论 对于无向图的邻接表来说，一条边对应两个单链表结点，邻接表结点总数是边数的2倍。 在无向图的邻接表中，各顶点对应的单链表的结点数（不算表头结点）就等于该顶点的度数。 在有向图邻接表中，一条弧对应一个表结点，表结点的数目和弧的数目相同。 在有向图邻接表中，单链表的结点数就等于相应顶点的出度数。 要求有向图中某顶点的入度数，需扫视邻接表的所有单链表，统计与顶点标号相应的结点个数。 建立的邻接表不是唯一的,与键盘输入边的顺序有关，输入的边的顺序不同，则得到的链表也不同。 在邻接表中容易找任一顶点的第一个邻接点和下一个邻接点，但要判定任意两顶点之间是否有边或弧，则需搜索第i个或第j个链表，不及邻接矩阵方便。,三、有向图的十字链表表示法 十字链表是将有向图的邻接表和逆邻接表结合起来的一种有向图链式存储结构。 结点结构 有向图的每一条弧有一个弧结点，每一个顶点必有一个顶点结点，其结构为：,2. 整体结构 通过hlink将弧头相同的弧连在一个链表上； 通过tlink将弧尾相同的弧连在一个链表上; hlink链和tlink链的头结点就是顶点结点。,例,特点： 顶点结点数=顶点数 ； 弧结点数=弧的条数 求入度：从顶点Vi的firstin出发，沿着弧结点中的hlink所经过的弧结点数 求出度：从顶点Vi的firstout出发，沿着弧结点中的tlink所经过的弧结点数,四、无向图的邻接多重表表示法 邻接多重表是无向图的另一种链式存储结构。 图的每一条边有一个边结点，边结点的结构为： 每一个顶点有一个顶点结点，顶点结点结构为： 其中：ivex 和jvex为该边所依附的两个顶点。 ilink指向下一条依附于顶点ivex的边。 jlink指向下一条依附于顶点jvex 的边。 data存放顶点的信息。 firstedge指向第一条依附于该顶点的边结点。,例,1,5,3,2,4,特点：顶点结点数为n，边结点数为e； 对需要得到边的两个顶点的一类操作很方便,7.3 图的遍历,和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有顶点各作一次访问。若给定的图是连通图，则从图中任一顶点出发顺着边可以访问到该图中所有的顶点，但是，在图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中可能还剩余有顶点没有访问到，因此，图的遍历较树的遍历更复杂。我们可以设置一个全局型标志数组visited来标志某个顶点是否被访过，未访问的值为0，访问过的值为1。根据搜索路径的方向不同，图的遍历有两种方法：深度优先搜索遍历和广度优先搜索遍历。,一、深度优先遍历(depth-first-search) 方法： 深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索遍历可定义如下： (1)首先访问顶点i，并将其访问标记置为访问过，即visitedi=1； (2)然后搜索与顶点i有边相连的下一个顶点j，若j未被访问过，则访问它，并将j的访问标记置为访问过，visitedj=1，然后从j开始重复此过程，若j已访问，再看与i有边相连的其它顶点； (3)若与i有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到图中所有顶点都被访问完止。 （4）深度优先搜索是一种递归的过程,深度遍历：V1 V2 V4 V8 V5 V6 V3 V7,V1,V2,V4,V5,V3,V7,V6,V8,例3,深度遍历：V1 V2 V4 V8 V3 V6 V7 V5,深度优先遍历算法,Ch6_1.c,V1,V2,V4,V5,V3,V7,V6,V8,例,深度遍历：V1,V3 ,V7 ,V6 ,V2 ,V5 ,V8 ,V4,V1,V2,V4,V5,V3,V7,V6,V8,例,深度遍历：V1,V3 ,V7 ,V6 ,V2 ,V4 ,V8 ,V5,void DFS(Graph G, int v0) / 从顶点v0出发，深度优先搜索遍历连通图 G Visited(v0); visitedv0 = TRUE; for(w=FirstAdjVex(G, v0); w!=0; w=NextAdjVex(G, v0,w) if (!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w / 递归调用DFS / DFS,void Traver (ALgraph *g) / 对图 G 作深度优先遍历。 int I; for (i=0; iG.vexnum; +i) visitedi = FALSE; / 访问标志数组初始化 for (i=0; iG.vexnum; +i) if (!visitedi) DFS(G,i); / 对尚未访问的顶点调用DFS ,二、广度优先遍历（breadth-first-search) 方法：广度优先搜索遍历类似于树的按层次遍历。设图G的初态是所有顶点均未访问，在G 中任选一顶点i作为初始点，则广度优先搜索的基本思想是： (1)首先访问顶点i，并将其访问标志置为已被访问，即visitedi=1； (2)接着依次访问与顶点i有边相连的所有顶点W1，W2，Wt； (3)然后再按顺序访问与W1，W2，Wt有边相连又未曾访问过的顶点；依此类推，直到图中所有顶点都被访问完为止 。,在广度优先搜索中，若对顶点V1的访问先于顶点V2的访问，则对V1邻接顶点的访问也先于V2邻接顶点的访问。就是说广度优先搜索中对邻接点的寻找具有“先进先出”的特性。因此，为了保证访问顶点的这种先后关系，需借助一个队列暂存那些刚访问过的顶点。 设此队列由一个一维数组构成，数组名为Queue，队首指针和队尾指针分别为front和rear。假设数组足够大，不必考虑有溢出的可能性。 广度优先搜索不是递归过程，不能用递归形式。,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,V1,V2,V4,V5,V3,V7,V6,V8,例3,广度遍历：V1 V2 V3 V4 V6 V7 V8 V5,广度优先遍历算法,Ch6_2.c,void BFS(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化访问标志 InitQueue(Q); / 置空的辅助队列Q if(!visitedv) EnQueue(Q, v); / v入队列,while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为u visitedu = TRUE; Visit(u); / 访问u for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 访问的顶点w入队列 / if / while /BFS,Void Traver(Mgragh *g) int i; for(i=0;ig.n;i+) visitedi=False; For(i=0;ig.n;i+) if(!visitedi) BFS(g,i); ,6.4 图的连通性问题 一、生成树 定义：在一个无向连通图G中，如果取它的全部顶点和一部分边构成一个子图G，若边集E(G)中的边刚好将图的所有顶点连通但又不形成环路，我们就称子图G是原图G的生成树。 由于n个顶点的连通图至少有n-1条边，而所有包含n-1 条边及n个顶点的连通图都是无回路的树，所以生成树是连通图中的极小连通子图，所谓极小是指边数最少，若在生成树中去掉任何一条边，都会使之变为非连通图，若在生成树上任意增加一条边，就会构成回路。那么，对给定的连通图，如何求得它的生成树呢？回到我们前面提到的图的遍历，访问过图中一个顶点后，要访问下一个顶点， 一般要求两个顶点有边相连，即必须经过图中的一条边，要遍历图中n 个顶点且每个顶点都只遍历一次，则必须经过图中的n-1条边，这n-1条边构成连通图的一个极小连通子图，所以它是连通图的生成树，由于遍历结果可能不唯一，所以得到的生成树也是不唯 一的。,深度优先生成树与广度优先生成树 要求得生成树，可考虑用深度优先搜索遍历及广度优先搜索遍历算法。对于深度优先搜索算法DFS，由DFS（i）递归到DFS（j），中间必经过一条边（i,j），因此，只需在DFS(j)调用前输出这条边，即可求得生成树的一条边，整个递归完成后，则可求得生成树的所有边。对于广度优先搜索算法BFS，若i 出队， j 入队，则(i,j)为一条树边。因此，可以在算法中输出这条边，算法完成后，将会输出n-1条边，也可求得生成树。由深度优先搜索遍历得到的生成树，称为深度优先生成树，由广度优先搜索遍历得到的生成树，称为广度优先生成树。 生成森林 若一个图是非连通图，但有若干个连通分量，则通过深度优先搜索遍历或广度优先搜索遍历，不可以得到生成树，但可以得到生成森林，且若非连通图有n个顶点，m个连通分量，则可以遍历得到m棵生成树，合起来为生成森林，森林中包含n-m条树边。,说明 一个图可以有许多棵不同的生成树 所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图 一个有n个顶点的连通图的生成树有n-1条边 生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路 含n个顶点n-1条边的图不一定是生成树,V1,V2,V4,V5,V3,V7,V6,V8,例,深度遍历：V1 V2 V4 V8 V5 V3 V6 V7,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,6.5最小生成树 1、问题提出 要在n个城市间建立通信联络网， 顶点表示城市 权 城市间建立通信线路所需花费代价 希望找到一棵生成树，它的每条边上的权值之和（即建立 该通信网所需花费的总代价）最小最小代价生成树 2、问题分析 n个城市间，最多可设置n(n-1)/2条线路 n个城市间建立通信网，只需n-1条线路 问题转化为：如何在可能的线路中选择n-1条，能把 所有城市（顶点）均连起来，且总耗费（各边权值之和）最小 3、定义 对于带权的连通图G，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为最小生成树,4、构造最小生成树方法 方法一：普里姆(Prim)算法 假设G=(V,E)是一个具有n 个顶点的连通网络，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空。 算法开始时，首先从V中任取一个顶点（假定为V1），将此顶点并入U中，此时最小生成树顶点集U=V1； 然后从那些其一个端点已在U中，另一个端点仍在U外的所有边中，找一条最短（即权值最小）的边，假定该边为(Vi,Vj),其中ViU，VjW(W=V-U),并把该边(Vi,Vj)和顶点Vj分别并入T的边集TE和顶点集U； 如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后，把所有n 个顶点都并入生成树T的顶点集U中，此时U=V，TE中包含有（n-1）条边； 这样，T就是最后得到的最小生成树。 普里姆算法中每次选取的边两端，总是一个已连通顶点（在U集合内）和一个未连通顶点（在U集合外），故这个边选取后一定能将未连通顶点连通而又保证不会形成环路。,Prim算法步骤 1. TE=,U=u0 2. 当UV，重复下列步骤： (1)选取（u0,v0)=mincost(u,v)|uU,vV-U，保证不形成回路; (2)TE=TE+（u0,v0), 边（u0,v0)并入TE; (3)U=U+V0，顶点V0 并入U,方法二：克鲁斯卡尔(Kruskal)算法 假设G =（V，E）是一个具有n个顶点的连通网络，T=(U,TE)是G 的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空集。 基本思想：将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成环路，则把它并入TE中，保留作为生成树T的一条边，若选取的边使生成树T形成环路，则将其舍弃，如此进行下去，直到TE中包含n-1条边为止。此时的T即为最小生成树。,Kruskal算法步骤 设N=（V，E）是个连通网, 算法步骤为： 1. 置生成树T的初始状态为T=（V，） 2. 当T中边数n-1时, 重复下列步骤: 从E中选取代价最小的边（v, u）, 并删除之; 若（v, u）依附的顶点v和u落在T中不同的连同分量上， 则将边（v, u）并入到T的边集中； 否则，舍去该边，选择下一条代价最小的边,一般来讲， 由于普里姆算法的时间复杂度为O(n2)，则适于稠密图；而克鲁斯卡尔算法需对e条边按权值进行排序，其时间复杂度为O(eloge)，则适于稀疏图。,7.5有向无环图及其应用 一、拓扑排序 1、概述 在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系： 先后关系，即必须在一子项目完成后，才能开始实施另一个子项目； 子项目之间无次序要求，即两个子项目可以同时进行，互不影响。 例如： 在工厂中，一件设备的生产包括许多工序，各工序之间也存在这两种关系。 学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。 这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个个顶点称之为活动(Activity)。 如果从顶点Vi到Vj之间存在有向边,则表示活动i必须先于活动j进行。这种图称做顶点表示活动的网络(Activity On Vertex network,简称AOV网络)。,在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。 AOV网络中一定不能有有向环路。例如在下图那样的有向环路中，V2是V3的前趋顶点，V1是V2的前趋顶点，V3又是V1的前趋顶点，环路表示顶点之间的先后关系进入了死循环。 因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环路网络在应用中才有实际意义。,2、定义 所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活动)排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得到满足。 由于AOV网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。 通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图G所有顶点都在拓扑排序序列中，则AOV网络必定不包含有有向环路。,3、拓扑排序方法 (1) 在网络中选择一个没有前趋的顶点，并把它输出； (2) 从网络中删去该顶点和从该顶点发出的所有有向边； (3) 重复执行上述两步，直到网中所有的顶点都被输出 (此时，原AOV网络中的所有顶点和边就都被删除掉了)。 如果进行到某一步，无法找到无前趋的顶点，则说明此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网的拓扑序列不是唯一的,4、算法实现 以邻接表作存储结构 把邻接表中所有入度为0的顶点进栈 栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈 重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕 为了实现拓扑排序的算法，对于给定的有向图，假定采用邻接表作为它的存储结构，每个顶点在邻接表中对应一个单链表，表示该顶点的各直接后继顶点。 规定将每个结点的Data域改为整型，并将每个链表的表头结点构成一个顺序表，各表头结点的Data域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得到。,5、算法描述,例,1,2,3,4,5,6,1,6,输出序列：6,输出序列：6,输出序列：6,输出序列：6,输出序列：6,输出序列：6,输出序列：6 1,输出序列：6 1,输出序列：6 1,4,输出序列：6 1,4,输出序列：6 1,4,输出序列：6 1,4,3,输出序列：6 1,4,3,输出序列：6 1,4,3,输出序列：6 1,4,3,输出序列：6 1,4,3,输出序列：6 1 3,4,3,输出序列：6 1 3,4,输出序列：6 1 3,4,输出序列：6 1 3,4,输出序列：6 1 3,4,2,输出序列：6 1 3,4,2,输出序列：6 1 3,4,2,输出序列：6 1 3 2,4,2,输出序列：6 1 3 2,4,输出序列：6 1 3 2 4,4,输出序列：6 1 3 2 4,输出序列：6 1 3 2 4,5,输出序列：6 1 3 2 4,5,输出序列：6 1 3 2 4 5,5,输出序列：6 1 3 2 4 5,二、关键路径 1、问题提出,把工程计划表示为有向图，用顶点表示事件，弧表示活动； 每个事件表示在它之前的活动已完成，在它之后的活动可以开始.,例 设一个工程有11项活动，9个事件 事件 V1表示整个工程开始 事件V9表示整个工程结束 整个工程只有一个开始点和一个完成点，在正常情况下，网中只一个入度为零的点（称为源点）和一个出度为零的点（称为汇点）。 问题：（1）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键？,2、定义 AOE网(Activity On Edge)也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。 路径长度路径上各活动持续时间之和。 关键路径路径长度最长的路径叫关键路径。 Ve(j)表示事件Vj的最早发生时间 Vl(j)表示事件Vj的最迟发生时间 e(i)表示活动ai的最早开始时间 l(i)表示活动ai的最迟开始时间 l(i)-e(i)表示完成活动ai的时间余量。 关键活动关键路径上的活动叫关键活动，即l(i)=e(i)的活动。,3、问题分析 如何找e(i)=l(i)的关键活动？,设活动ai用弧表示，其持续时间记为：dut() 则有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut(),(1)从Ve(1)=Vl1)=0开始向前递推,(2)从Vl(n)=Ve(n)=整个工程完成的最长时间，开始向后递推,此公式的意义为：由从Vi顶点指出的各边所代表的活动中取需最早开始的一个开始时间作为Vi的最迟出现时间。,此式的意义为：从指向顶点Vj的各边的活动中取最晚完成的一个活动的完成时间作为Vj的最早出现时间。,3、求关键路径步骤 求Ve(i) 求Vl(j) 求e(i) 求l(i) 计算l(i)-e(i),9,8,7,6,4,5,3,2,1,a2=4,a3=5,a5=1,a6=2,a9=4,a1=6,a4=1,a7=9,a8=7,a10=2,a11=4,V1 V2 V3 V4 V5 V6 V7 V8 V9,0 6 4 5 7 7 16 14 18,0 6 6 8 7 10 16 14 18,a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11, ,4、算法实现 以邻接表作存储结构 从源点V1出发，令Ve1=0,按拓扑序列求各顶点的Vei 从汇点Vn出发，令Vln=Ven,按逆拓扑序列求其余各顶点的Vli 根据各顶点的Ve和Vl值，计算每条弧的ei和li,找出ei=li的关键活动,5、算法描述 输入顶点和弧信息，建立其邻接表 计算每个顶点的入度 对其进行拓扑排序 排序过程中求顶点的Vei 将得到的拓扑序列进栈(设栈的目的是为了得到一个逆拓扑排序） 按逆拓扑序列求顶点的Vli 计算每条弧的ei和li,找出ei=li的关键活动,6、结论： 关键路径上的活动都是关键活动； 缩短非关键活动都不能缩短整个工期； 分析关键路径的目的是找出影响整个工期的关键活动，缩短关键活动的持续时间，常可以缩短整个工期； 在有多条关键路径时，缩短那些在所有关键路径上的关键活动，才能缩短整个工期。,6.6 最短路径 1、问题提出,用带权的有向图表示一个交通运输网，图中： 顶点表示城市 边表示城市间的交通联系 权表示此线路的长度或沿此线路运输所花的时间或费用等 问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中， 各边上权值之和最小的一条路径最短路径,2、从某个源点到其余各顶点的最短路径,13,8,13,19,21,20,迪杰斯特拉(Dijkstra)算法思想,按路径长度递增次序产生最短路径算法： 把V分成两组： （1）S：已求出最短路径的顶点的集合； （2） T = V-S：尚未确定最短路径的顶点集合。 将T中顶点按最短路径递增的次序加入到S中。,如何将T中顶点加到S中？ V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。,具体描述： 迪