有向无环图的应用.pptx

《有向无环图的应用.pptx》由会员分享，可在线阅读，更多相关《有向无环图的应用.pptx（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、7.5 7.5 有向无环图及其应用有向无环图及其应用 有向无环图有向无环图(directed acycline(directed acycline graph)graph)简称简称DAGDAG图，是描述一项工程或系统的图，是描述一项工程或系统的进行过程的有效工具。进行过程的有效工具。第1页/共18页 对整个工程和系统，人们关心的是两个方对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行；二是估算面的问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间。整个工程完成所必须的最短时间。有向无环图的应用：有向无环图的应用：n拓扑排序拓扑排序n关键路径关键路径第2页/共18

2、页 在工程实践中，一个工程项目往往由若干在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：个子项目组成，这些子项目间往往有多种关系：先后关系，即必须在一子项目完成后，先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；才能开始实施另一个子项目；子项目之间无次序要求，即两个子项目子项目之间无次序要求，即两个子项目可以同时进行，互不影响。可以同时进行，互不影响。第3页/共18页 我们用一种有向图来表示上述问题。在这种有向图中，顶点表示活动，有我们用一种有向图来表示上述问题。在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这种有向图叫做顶点表示活动的网络向

3、边表示活动的优先关系，这种有向图叫做顶点表示活动的网络(Activity On(Activity On Vertex Network)Vertex Network)简称为简称为AOVAOV网网。7.5.1 7.5.1 拓扑排序拓扑排序第4页/共18页课程编号课程编号课程名称课程名称先导课程编号先导课程编号C1C1程序设计基础程序设计基础无无C2C2离散数学离散数学C1C1C3C3数据结构数据结构C1C1，C2C2C4C4汇编语言汇编语言C1C1C5C5算法分析与设计算法分析与设计C3C3，C4C4C6C6计算机组成原理计算机组成原理C11C11C7C7编译原理编译原理C5C5，C3C3C8C8

4、操作系统操作系统C3C3，C6C6C9C9高等数学高等数学无无C C 1010线性代数线性代数C9C9C11C11普通物理普通物理C9C9C12C12数值分析数值分析C9C9，C10C10，C1C1第5页/共18页课程先后关系如图：课程先后关系如图：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c2第6页/共18页n 在在AOVAOV网络中，如果顶点网络中，如果顶点V Vi i的活动必须在顶点的活动必须在顶点V Vj j的活动以的活动以前进行，则称前进行，则称V Vi i为为V Vj j的前趋顶点，而称的前趋顶点，而称V Vj j为为V

5、Vi i的后继顶点。的后继顶点。这种前趋后继关系有这种前趋后继关系有传递性传递性。此外，任何活动。此外，任何活动i i不能以它自不能以它自己作为自己的前驱或后继，这叫做己作为自己的前驱或后继，这叫做反自反性反自反性。n 从前驱和后继的传递性和反自反性来看，从前驱和后继的传递性和反自反性来看，AOVAOV网中不能网中不能出现回路出现回路(有向环有向环)，回路表示顶点之间的先后关系进入了，回路表示顶点之间的先后关系进入了死循环。死循环。n 判断判断AOVAOV网是否有有向环的方法是对该网是否有有向环的方法是对该AOVAOV网进行拓扑排网进行拓扑排序，将序，将AOVAOV网中顶点排列成一个线性有序序

6、列，若该线性序网中顶点排列成一个线性有序序列，若该线性序列中包含列中包含AOVAOV网全部顶点，则网全部顶点，则AOVAOV网无环，否则，网无环，否则，AOVAOV网中存网中存在有向环，该在有向环，该AOVAOV网所代表的工程是不可行的。网所代表的工程是不可行的。第7页/共18页何谓何谓“拓扑排序拓扑排序”？n拓扑序列：拓扑序列：在在AOVAOV网中，若不存在回路，则所有活动可排列网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓动都排在该活动的前面，我们把此序列叫做拓扑序列。扑序列。n拓

7、扑排序拓扑排序 由由AOVAOV网构造拓扑序列的过程叫拓扑排序。网构造拓扑序列的过程叫拓扑排序。AOVAOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的，满足上述定义的任，满足上述定义的任一线性序列都称为它的拓扑序列。一线性序列都称为它的拓扑序列。第8页/共18页拓扑有序序列：拓扑有序序列：（C1C1，C2C2，C3C3，C4C4，C5C5，C8C8，C9C9，C7C7，C6C6）（C2C2，C5C5，C1C1，C8C8，C3C3，C9C9，C4C4，C7C7，C6C6）第9页/共18页如何进行拓扑排序？如何进行拓扑排序？解决方法：解决方法：1 1）从有向图中选取一个没有前驱的顶点，并）从有向

8、图中选取一个没有前驱的顶点，并输出之；输出之；2 2）从有向图中删去此顶点以及所有以它为尾）从有向图中删去此顶点以及所有以它为尾的弧；的弧；3 3）重复上述两步，直至图空，或者图不空但）重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。后一种情况说明有向找不到无前驱的顶点为止。后一种情况说明有向图中存在环。图中存在环。第10页/共18页如何在计算机中实现如何在计算机中实现 拓扑排序呢？拓扑排序呢？第11页/共18页拓扑排序算法的实现拓扑排序算法的实现n为了实现拓扑排序的算法，对给定的有向图可采用邻为了实现拓扑排序的算法，对给定的有向图可采用邻接表作为它的存储结构。接表作为它的存储结构

9、。n将每个链表的表头结点构成一个顺序表，各表头结点将每个链表的表头结点构成一个顺序表，各表头结点的的DataData域存放相应顶点的入度值。每个顶点入度初值域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得到。可随邻接表动态生成过程中累计得到。n在拓扑排序过程中，凡入度为零的顶点即是没有前趋在拓扑排序过程中，凡入度为零的顶点即是没有前趋的顶点，可将其取出列入有序序列中，同时将该顶点的顶点，可将其取出列入有序序列中，同时将该顶点从图中删除掉不再考虑。从图中删除掉不再考虑。n删去一个顶点时，所有它的直接后继顶点入度均减删去一个顶点时，所有它的直接后继顶点入度均减1 1，表示相应

10、的有向边也被删除掉。，表示相应的有向边也被删除掉。n设置一个堆栈，将已检验到的入度为零的顶点标号进设置一个堆栈，将已检验到的入度为零的顶点标号进栈，当再出现新的无前趋顶点时，也陆续将其进栈。栈，当再出现新的无前趋顶点时，也陆续将其进栈。每次选入度为零的顶点时，只要取栈顶顶点即可。每次选入度为零的顶点时，只要取栈顶顶点即可。第12页/共18页4004 2100314 AOVAOV网络的邻接表网络的邻接表01234顶点的入度顶点的入度数组下标数组下标第13页/共18页用邻接表存储用邻接表存储AOVAOV网络，拓扑排序算法描述：网络，拓扑排序算法描述：(1)(1)把邻接表中所有入度为零的顶点进栈；把

11、邻接表中所有入度为零的顶点进栈；(2)(2)在栈不空时：在栈不空时：退栈并输出栈顶的顶点退栈并输出栈顶的顶点 j j；在邻接表的第在邻接表的第 j j 个单链表中，查找顶点个单链表中，查找顶点为为 j j 的所有直接后继顶点的所有直接后继顶点 k k，并将，并将 k k 的入度减的入度减1 1。若顶点。若顶点 k k 的入度为零，则顶点的入度为零，则顶点 k k 进栈；进栈；若栈空时输出的顶点个数不是若栈空时输出的顶点个数不是 n n，则有向，则有向图中有环路，否则拓扑排序完毕。图中有环路，否则拓扑排序完毕。第14页/共18页拓扑排序算法拓扑排序算法Status Topological Sor

12、t(ALGraph G)Status Topological Sort(ALGraph G)/有向图有向图G G采用邻接表存储结构。若采用邻接表存储结构。若G G无回路，无回路，/则输出则输出G G的顶点的的顶点的1 1个拓扑序列并返回个拓扑序列并返回OKOK，否则，否则ERRORERROR FindInDegree(GFindInDegree(G，indegree)indegree)；/对各顶点求入度对各顶点求入度indegree0.vernum-indegree0.vernum-11 InitStack(S)InitStack(S)；for(i=0for(i=0；iG.vexnuminex

13、tarc)nextarc)k=p-adjvexk=p-adjvex；/对对i i号顶点的每个邻接点入号顶点的每个邻接点入度减度减1 1if(if(！(-indegreek)Push(S(-indegreek)Push(S，k);k);/若入度减为若入度减为0 0，则，则入栈入栈 /for/for/while/whileif(countG.vexnum)return ERROR;if(countG.vexnum)return ERROR;/该有向图该有向图有回路有回路else return OKelse return OK；/TopologicalSort/TopologicalSort 第16

14、页/共18页分析：分析：对有对有 n n 个顶点和个顶点和 e e 条弧的有向图而言，条弧的有向图而言，建立求各顶点的入度的时间复杂度为建立求各顶点的入度的时间复杂度为O(e)O(e)；建；建零入度顶点栈的时间复杂度为零入度顶点栈的时间复杂度为O(n)O(n)；在拓扑排；在拓扑排序过程中，若有向图无环，则每个顶点进一次序过程中，若有向图无环，则每个顶点进一次栈，出一次栈，入度减栈，出一次栈，入度减1 1的操作在的操作在 WHILEWHILE语句中语句中总共执行总共执行e e次，所以，总的时间复杂度为次，所以，总的时间复杂度为O(n+e)O(n+e)。拓扑排序的算法是下一讲讨论的求关键路径拓扑排序的算法是下一讲讨论的求关键路径的基础。的基础。第17页/共18页感谢您的观看！第18页/共18页