数据结构第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,v4 E=(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=v0 v1,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,(1jn)路径长度沿路径边的数目或沿路径各边权值之和 回路第一个顶点和最后一个顶点相同的路径叫 在图G1中，V0,V1,V2,V3 是V0到V3的路径；V0,V1,V2,V3,V0是回路；在图G2中，V0,V2,V3 是V0到V3的路径；V0,V2,V3,V0是回路；,无向图G1,有向图G2,例,7.1 图的基本概念,5 简单路径和简单回路 在一条路径中,序列中顶点不重复出现的路径称为简单路径；由简单路径组成的回路称为简单回路；在图G1中，V0,V1,V2,V3 是简单路径；在图G2中，V0,V2,V3,V0是简单回路；,无向图G1,有向图G2,例,7.1 图的基本概念,6 连通图（强连通图）在无（有）向图G=中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图（强连通图）,7.1 图的基本概念,非连通图,连通图,强连通图,非强连通图,7 子图 设有两个图G=（V，E）、G1=（V1，E1），若V1 V，E1 E，则称 G1是G的子图；例(b)、(c)是(a)的子图,(a),(b),(c),7.1 图的基本概念,8 连通分量（强连通分量）无向图G 的极大连通子图称为G的连通分量 极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通；,连通分量,非连通图,7.1 图的基本概念,有向图D 的极大强连通子图称为D 的强连通分量 极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的；,9 生成树 包含无向图G 所有顶点的的极小连通子图称为G 的生成树 极小连通子图意思是：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通，若T是G 的生成树当且仅当T 满足如下条件 T是G 的连通子图 T包含G 的所有顶点 T中无回路,连通图 G1,G1的生成树,7.1 图的基本概念,T1是G1的生成树,图G1中：V(G1)=1,2,3,4,5,6 E(G1)=,图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),3,4,1,3,1,0,路径：1，2，3，5，6，3路径长度：简单路径：1，2，3，5，6，3，1 3，5，6，3,路径：1，2，5，7，6，5，2，3路径长度：7简单路径：回路：简单回路：,5,1，2，3，5，6,回路：,简单回路：,1，2，5，7，6,1，2，3，1,1，2，5，7，6，5，2，1,连通图,强连通图,非连通图连通分量,7.2 图的存储结构多重链表,邻接矩阵表示顶点间相联关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵,数组表示法,特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行(或第i列)元素之和有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和,检测图中的总边数。扫描整个数组A，统计出数组中非0元素的个数。无向图的总边数为非0元素个数的一半，而有向图的总弧数为非0元素个数；,网的邻接矩阵可定义为：,其中 wij表示(vi,vj)边上的权值；表示结点vi和vj之间没有边相连。,若G是一个带权值的图，即为网络，则其邻接矩阵可定义为：,带权有向图的邻接矩阵,带权无向图的邻接矩阵,邻接矩阵表示法中图的存储表示#define n 6/*图的顶点数*/#define e 8/*图的边数*/typedef char vextype;/*顶点的数据类型*/typedef float adjtype;/*权值类型*/typedef struct vextype vexsn;adjtype arcsnn;graph;,2,1,4,3,5,B,A,D,C,E,2,1,5,3,4,0,=,80,70,80,70,50,40,50,30,40,20,30,20,arcs,6,20,30,50,40,70,80,邻接矩阵表示法中无向网络的建立算法CREATEGRAPH(graph*ga)int i,j,k;float w;for(i=0;ivexsigetchar();/*读入顶点信息，建立顶点表*/for(i=0;iarcsij0;/*邻接矩阵初始化*/for(k=0;karcsijw;ga-arcsjiw;,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。,邻接矩阵法优点：,邻接矩阵法缺点：,注：用两个数组分别存储顶点表和邻接矩阵#define INFINITY INT_MAX/最大值#define MAX_VERTEX_NUM 20/假设的最大顶点数typedef enum DG,DN,AG,AN GraphKind;/有向/无向图，有向/无向网typedef struct ArcCell/弧（边）结点的定义 VRType adj;/顶点间关系，无权图取1或0；有权图取权值类型 InfoType*info;/该弧相关信息的指针ArcCell,AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct/图的定义VertexType vexs MAX_VERTEX_NUM;/顶点表，用一维向量即可AdjMatrix arcs;/邻接矩阵int Vernum,arcnum;/顶点总数，弧（边）总数GraphKind kind;/图的种类标志Mgraph;,图的邻接矩阵存储表示（参见教材P161）,对于n个顶点的图或网，空间效率=O(n2),Status CreateUDN(Mgraph/CreateUDN,例：用邻接矩阵生成无向网的算法（参见教材P162）,对于n个顶点e条弧的网，建网时间效率=O(n2+n+e*n),邻接表(Adjacency List),在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边。每个结点由三个域组成：,邻接点域,指示与顶点vi邻接的点在图中的位置,链域,指示下一条边或弧的结点,数据域,存储与边或弧相关的信息，如权值，无权图一般不用,每个单链表附设一个头结点。在表头结点中，除了设有链域指向链表中第一个结点之外，还设有存储顶点vi的名或其它有关信息的数据域。,数据域,链域,表头结点可以链相接，通常以顺序结构的形式存储，以便随机访问任一顶点的链表。,存放与该顶点相关的信息,指示第一条依附于该顶点的边的指针,图的邻接表存储表示,#define MAX_VERTEX_NUM 20typedef 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;,无向图的邻接表,在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数。,有向图的邻接表(出边表),有向图中对每个结点建立以Vi为尾的弧的单链表顶点：用一维数组存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储,有向图的逆邻接表(入边表),有向图中对每个结点建立以Vi为头的弧的单链表顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储,在有向图中，第i 个链表中的结点个数只是顶点vi的出度，为求入度，必须遍历整个邻接表。在所有链表中其邻接点域的值为i 的结点的个数是顶点vi的入度。在有向图的邻接表中，第 i 个边链表链接的边都是顶点 i 发出的边。也叫做出边表。在有向图的逆邻接表中，第 i 个边链表链接的边都是进入顶点 i 的边。也叫做入边表。,该结点表示边（Vi Vj）,其中的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 图的遍历,从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次。这一过程就称为图的遍历。图的遍历比树的遍历要复杂得多。因为图的任一顶点都可能和其余的顶点相邻接；因此在访问了某个顶点后，可能沿着某条路径搜索后，又回到该顶点上。为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。,为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited 0.n-1，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited i 为 1，防止它被多次访问。,通常有两条遍历图的路径：深度优先搜索、广度优先搜索,深度优先搜索DFS(Depth_First Search),算法思想：假设初始状态是图中所有顶点未曾被访问，则可从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,图的深度优先搜索类似于树的前序遍历,深度优先搜索的示例,由上得到顶点访问序列为：v1、v2、v4、v8、v5、v3、v6、v7,显然这是一个递归的过程，为了在遍历过程中便于区分顶点是否已被访问，需附设访问数组visited 0.n-1，数组元素的初始值为false；在遍历过程中，一旦某一个顶点 i 被访问，则置 visited i 为 true。,例2：,v2 v1 v3 v5,DFS 结果,v4 v6,起点,深度优先搜索（遍历）步骤：,详细归纳：在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻接但还未被访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。,简单归纳：访问起始点 v;若v的第1个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找v的第2个邻接点重新遍历。,接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。,Boolean visitedMAX;/访问标志数组 Status(*VisitFunc)(int v);/函数变量/以上两个变量都是全局变量void DFSTraverse(Graph G,Status(*Visit)(int v)/对图G作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用DFS,图的深度优先搜索算法,void DFS(Graph G,int v)/从第v个顶点出发递归地深度优先遍历图G。visitedv=TRUE;/访问标记置为true VisitFunc(v);/访问第v个顶点 for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w/递归调用DFS,算法时间复杂度分析,从上述算法可知，在遍历过程中，对图中每个顶点至多调用一次DFS函数；因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，对图的遍历实际上是对每个顶点查找其邻接点的过程，耗费的时间取决于所用的存储结构。,如果用邻接表表示图，沿 Firstout link 链可以找到某个顶点 v 的所有邻接顶点 w。由于总共有 2e 个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。,广度优先搜索BFS(Breadth_First Search),图的广度优先搜索类似于树的按层次遍历过程,算法思想：从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,广度优先搜索的示例,由上得到顶点访问序列为：v1、v2、v3、v4、v5、v6、v7、v8,为了实现对图的逐层访问，需要在算法中使用一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。为避免重复访问，还需要一个辅助数组 visited 0.n-1，给被访问过的顶点加标记。,例2：,v3,BFS 结果,v4 v5,v2 v1 v6,v9 v8 v7,起点,广度优先搜索（遍历）步骤：,简单归纳：在访问了起始点v之后，依次访问 v的邻接点；然后再依次访问这些顶点中未被访问过的邻接点；直到所有顶点都被访问过为止。,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,图的广度优先搜索算法,void BFSTraverse(Graph G,Status(*Visit)(int v)/按广度优先非递归遍历图G。/使用辅助队列Q和访问标志数组visited。for(v=0;vG.vexnum;+v)visitedv=FALSE;InitQueue(Q);/置空的辅助队列Q for(v=0;vG.vexnum;+v)if(!visitedv)/若顶点v尚未被访问 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)/u的尚未访问的邻接点w入队 visitedw=TRUE;Visit(w);/访问w EnQueue(Q,w);/if/while/if/BFSTraverse,如果使用邻接表表示图，则循环的总时间代价为 d0+d1+dn-1=O(e)，其中的 di 是顶点 i 的度。如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。,算法时间复杂度分析,7.4 图的连通性,当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图(连通分量)的所有顶点。若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。,例,图G4,G4的三个连通分量,在以上算法中，需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。,对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。,最小生成树(minimum cost spanning tree),使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，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具有最小代价的边。,struct VertexType adjvex;/存储该边依附的在U中的顶点 VRType lowcost;/存储该边上的权 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,C2 C4 数据结构 C3,C2 C5 高级语言程序设计 C2 C6 编译方法 C5,C4 C7 操作系统 C4,C9 C8 普通物理 C1 C9 计算机原理 C8,课程代号,课程名称,先修课程,表示课程之间优先关系的有向图,由上可知，可用有向图表示一个工程。,在这种有向图中，用顶点表示活动，用有向边表示活动。Vi 必须先于活动Vj 进行。这种有向图叫做顶点表示活动的AOV网络(Activity On Vertices)。,因此，对给定的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，则有向图有环；否则，拓扑排序完毕,邻接表结点：typedef struct node int vex;/顶点域 struct node*next;/链域JD;,表头结点：typedef struct tnode int in;/入度域 struct node*link;/链域TD;TD gM;/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,输出序列：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,分析此拓扑排序算法可知，如果AOV网络有n 个顶点，e 条边，在拓扑排序的过程中，搜索入度为零的顶点，建立链式栈所需要的时间是O(n)。在正常的情况下，有向图有 n 个顶点，每个顶点进一次栈，出一次栈，共输出 n 次。顶点入度减一的运算共执行了 e 次。所以总的时间复杂度为O(n+e)。,算法时间复杂度分析,关键路径,如果在带权有向无环图中 用有向边表示一个工程中的活动(Activity)用边上权值表示活动持续时间(Duration)用顶点表示事件(Event)则这样的有向图叫做用边表示活动的网络，简称 AOE(Activity On Edges)网络。,一个AOE网络,AOE网络在某些工程估算方面非常有用，可以使人们了解：(1)完成整个工程至少需要多少时间(假设网络中没有环)?(2)为缩短完成工程所需的时间,应当加快哪些活动?,在AOE网络中,有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条；这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。,因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。,要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。,关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径。,几个与计算关键活动有关的量：,事件Vi 的最早可能开始时间Ve(i)是从源点V0 到顶点Vi 的最长路径长度。事件Vi 的最迟允许开始时间Vli 是在保证汇点Vn-1 在Ven-1 时刻完成的前提下，事件Vi 的允许的最迟开始时间。,活动ak 的最早可能开始时间 ek 设活动ak 在边上，则ek是从源点V0到顶点Vi 的最长路径长度。因此,ek=Vei。活动ak 的最迟允许开始时间 lk lk是在不会引起时间延误的前提下，该活动允许的最迟开始时间。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,按逆拓扑序列求其余各顶点的V