有向无环图的应用.ppt

第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径,7.5 有向无环图及其应用,有向无环图(directed acycline graph)简称DAG图，是描述一项工程或系统的进行过程的有效工具。,对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间。 有向无环图的应用： 拓扑排序 关键路径,在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系： 先后关系，即必须在一子项目完成后，才能开始实施另一个子项目； 子项目之间无次序要求，即两个子项目可以同时进行，互不影响。,我们用一种有向图来表示上述问题。在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这种有向图叫做顶点表示活动的网络(Activity On Vertex Network)简称为AOV网。,7.5.1 拓扑排序,课程先后关系如图：,c1,c9,c4,c2,c12,c10,c5,c3,c6,c7,c8,c2,在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。此外，任何活动i不能以它自己作为自己的前驱或后继，这叫做反自反性。 从前驱和后继的传递性和反自反性来看，AOV网中不能出现回路(有向环)，回路表示顶点之间的先后关系进入了死循环。 判断AOV网是否有有向环的方法是对该AOV网进行拓扑排序，将AOV网中顶点排列成一个线性有序序列，若该线性序列中包含AOV网全部顶点，则AOV网无环，否则，AOV网中存在有向环，该AOV网所代表的工程是不可行的。,何谓“拓扑排序” ？,拓扑序列： 在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列。 拓扑排序 由AOV网构造拓扑序列的过程叫拓扑排序。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称为它的拓扑序列。,拓扑有序序列： （C1，C2，C3，C4，C5，C8，C9，C7，C6） （C2，C5，C1，C8，C3，C9，C4，C7，C6）,如何进行拓扑排序？,解决方法： 1）从有向图中选取一个没有前驱的顶点，并输出之； 2）从有向图中删去此顶点以及所有以它为尾的弧； 3）重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。后一种情况说明有向图中存在环。,如何在计算机中实现 拓扑排序呢？,拓扑排序算法的实现,为了实现拓扑排序的算法，对给定的有向图可采用邻接表作为它的存储结构。 将每个链表的表头结点构成一个顺序表，各表头结点的Data域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得到。 在拓扑排序过程中，凡入度为零的顶点即是没有前趋的顶点，可将其取出列入有序序列中，同时将该顶点从图中删除掉不再考虑。 删去一个顶点时，所有它的直接后继顶点入度均减1，表示相应的有向边也被删除掉。 设置一个堆栈，将已检验到的入度为零的顶点标号进栈，当再出现新的无前趋顶点时，也陆续将其进栈。每次选入度为零的顶点时，只要取栈顶顶点即可。,4,0,0,4,2,1,0,0,3,1,4,AOV网络的邻接表,0 1 2 3 4,顶点的入度,数组下标,用邻接表存储AOV网络，拓扑排序算法描述：,(1) 把邻接表中所有入度为零的顶点进栈； (2) 在栈不空时： 退栈并输出栈顶的顶点 j； 在邻接表的第 j 个单链表中，查找顶点为 j 的所有直接后继顶点 k，并将 k 的入度减1。若顶点 k 的入度为零，则顶点 k 进栈； 若栈空时输出的顶点个数不是 n，则有向图中有环路，否则拓扑排序完毕。,拓扑排序算法 Status Topological Sort(ALGraph G) /有向图G采用邻接表存储结构。若G无回路， /则输出G的顶点的1个拓扑序列并返回OK，否则ERROR FindInDegree(G，indegree)； /对各顶点求入度indegree0vernum-1 InitStack(S)； for(i=0；iG.vexnum； +i)/建零入度顶点栈 if(!indegreei)Push(S，i) /入度为0者进栈 count=0； /对输出顶点计数,while (!StackEmpty(S) Pop(S，i); printf(i，G.verticesi.data); +count; /输出i号顶点并计数 for(p=G.verticesi.firstarc; p; p=p-nextarc) k=p-adjvex；/对i号顶点的每个邻接点入度减1 if(！(-indegreek)Push(S，k); /若入度减为0，则入栈 /for /while if(countG.vexnum) return ERROR;/该有向图有回路 else return OK； /TopologicalSort,分析： 对有 n 个顶点和 e 条弧的有向图而言，建立求各顶点的入度的时间复杂度为O(e)；建零入度