《《有向无环图的应用》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《有向无环图的应用》PPT课件.ppt（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第7 7章章 图图7.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储结构图的存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性问题图的连通性问题7.5 7.5 有向无环图及其应用有向无环图及其应用7.6 7.6 最短路径最短路径7.5 7.5 有向无环图及其应用有向无环图及其应用 有向无环图有向无环图(directed acycline graph)(directed acycline graph)简简称称DAGDAG图，是描述一项工程或系统的进行过程的图，是描述一项工程或系统的进行过程的有效工具。有效工具。对整个工程和系统，人们关心的是两个方面对整个工程和
2、系统，人们关心的是两个方面的问题：一是工程能否顺利进行；二是估算整个的问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间。工程完成所必须的最短时间。有向无环图的应用：有向无环图的应用：n拓扑排序拓扑排序n关键路径关键路径 在工程实践中，一个工程项目往往由若干个在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：子项目组成，这些子项目间往往有多种关系：先后关系，即必须在一子项目完成后，才先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；能开始实施另一个子项目；子项目之间无次序要求，即两个子项目可子项目之间无次序要求，即两个子项目可以同时进行，互不
3、影响。以同时进行，互不影响。我们用一种有向图来表示上述问题。在我们用一种有向图来表示上述问题。在这种有向图中，顶点表示活动，有向边表示这种有向图中，顶点表示活动，有向边表示活动的优先关系，这种有向图叫做顶点表示活动的优先关系，这种有向图叫做顶点表示活动的网络活动的网络(Activity On Vertex Network)(Activity On Vertex Network)简称为简称为AOVAOV网网。7.5.1 7.5.1 拓扑排序拓扑排序课程编号课程编号课程名称课程名称先导课程编号先导课程编号C1C1程序设计基础程序设计基础无无C2C2离散数学离散数学C1C1C3C3数据结构数据结构C
4、1C1，C2C2C4C4汇编语言汇编语言C1C1C5C5算法分析与设计算法分析与设计C3C3，C4C4C6C6计算机组成原理计算机组成原理C11C11C7C7编译原理编译原理C5C5，C3C3C8C8操作系统操作系统C3C3，C6C6C9C9高等数学高等数学无无C C 1010线性代数线性代数C9C9C11C11普通物理普通物理C9C9C12C12数值分析数值分析C9C9，C10C10，C1C1课程先后关系如图：课程先后关系如图：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c2n 在在AOVAOV网络中，如果顶点网络中，如果顶点V Vi
5、 i的活动必须在顶点的活动必须在顶点V Vj j的活动以的活动以前进行，则称前进行，则称V Vi i为为V Vj j的前趋顶点，而称的前趋顶点，而称V Vj j为为V Vi i的后继顶点。的后继顶点。这种前趋后继关系有这种前趋后继关系有传递性传递性。此外，任何活动。此外，任何活动i i不能以它自不能以它自己作为自己的前驱或后继，这叫做己作为自己的前驱或后继，这叫做反自反性反自反性。n 从前驱和后继的传递性和反自反性来看，从前驱和后继的传递性和反自反性来看，AOVAOV网中不能网中不能出现回路出现回路(有向环有向环)，回路表示顶点之间的先后关系进入了，回路表示顶点之间的先后关系进入了死循环。死循
6、环。n 判断判断AOVAOV网是否有有向环的方法是对该网是否有有向环的方法是对该AOVAOV网进行拓扑排网进行拓扑排序，将序，将AOVAOV网中顶点排列成一个线性有序序列，若该线性序网中顶点排列成一个线性有序序列，若该线性序列中包含列中包含AOVAOV网全部顶点，则网全部顶点，则AOVAOV网无环，否则，网无环，否则，AOVAOV网中存网中存在有向环，该在有向环，该AOVAOV网所代表的工程是不可行的。网所代表的工程是不可行的。何谓何谓“拓扑排序拓扑排序”？n拓扑序列：拓扑序列：在在AOVAOV网中，若不存在回路，则所有活动可排列网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动
7、的所有前驱活成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓动都排在该活动的前面，我们把此序列叫做拓扑序列。扑序列。n拓扑排序拓扑排序 由由AOVAOV网构造拓扑序列的过程叫拓扑排序。网构造拓扑序列的过程叫拓扑排序。AOVAOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的，满足上述定义的任，满足上述定义的任一线性序列都称为它的拓扑序列。一线性序列都称为它的拓扑序列。拓扑有序序列：拓扑有序序列：（C1C1，C2C2，C3C3，C4C4，C5C5，C8C8，C9C9，C7C7，C6C6）（C2C2，C5C5，C1C1，C8C8，C3C3，C9C9，C4C4，C7C7
8、，C6C6）如何进行拓扑排序？如何进行拓扑排序？解决方法：解决方法：1 1）从有向图中选取一个没有前驱的顶点，并）从有向图中选取一个没有前驱的顶点，并输出之；输出之；2 2）从有向图中删去此顶点以及所有以它为尾）从有向图中删去此顶点以及所有以它为尾的弧；的弧；3 3）重复上述两步，直至图空，或者图不空但）重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。后一种情况说明有向找不到无前驱的顶点为止。后一种情况说明有向图中存在环。图中存在环。如何在计算机中实现如何在计算机中实现 拓扑排序呢？拓扑排序呢？拓扑排序算法的实现拓扑排序算法的实现n为了实现拓扑排序的算法，对给定的有向图可采用邻为了
9、实现拓扑排序的算法，对给定的有向图可采用邻接表作为它的存储结构。接表作为它的存储结构。n将每个链表的表头结点构成一个顺序表，各表头结点将每个链表的表头结点构成一个顺序表，各表头结点的的DataData域存放相应顶点的入度值。每个顶点入度初值域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得到。可随邻接表动态生成过程中累计得到。n在拓扑排序过程中，凡入度为零的顶点即是没有前趋在拓扑排序过程中，凡入度为零的顶点即是没有前趋的顶点，可将其取出列入有序序列中，同时将该顶点的顶点，可将其取出列入有序序列中，同时将该顶点从图中删除掉不再考虑。从图中删除掉不再考虑。n删去一个顶点时，所有
10、它的直接后继顶点入度均减删去一个顶点时，所有它的直接后继顶点入度均减1 1，表示相应的有向边也被删除掉。，表示相应的有向边也被删除掉。n设置一个堆栈，将已检验到的入度为零的顶点标号进设置一个堆栈，将已检验到的入度为零的顶点标号进栈，当再出现新的无前趋顶点时，也陆续将其进栈。栈，当再出现新的无前趋顶点时，也陆续将其进栈。每次选入度为零的顶点时，只要取栈顶顶点即可。每次选入度为零的顶点时，只要取栈顶顶点即可。4004 2100314 AOVAOV网络的邻接表网络的邻接表01234顶点的入度顶点的入度数组下标数组下标用邻接表存储用邻接表存储AOVAOV网络，拓扑排序算法描述：网络，拓扑排序算法描述：
11、(1)(1)把邻接表中所有入度为零的顶点进栈；把邻接表中所有入度为零的顶点进栈；(2)(2)在栈不空时：在栈不空时：退栈并输出栈顶的顶点退栈并输出栈顶的顶点 j j；在邻接表的第在邻接表的第 j j 个单链表中，查找顶点个单链表中，查找顶点为为 j j 的所有直接后继顶点的所有直接后继顶点 k k，并将，并将 k k 的入度减的入度减1 1。若顶点若顶点 k k 的入度为零，则顶点的入度为零，则顶点 k k 进栈；进栈；若栈空时输出的顶点个数不是若栈空时输出的顶点个数不是 n n，则有向，则有向图中有环路，否则拓扑排序完毕。图中有环路，否则拓扑排序完毕。拓扑排序算法拓扑排序算法Status T
12、opological Sort(ALGraph G)Status Topological Sort(ALGraph G)/有向图有向图G G采用邻接表存储结构。若采用邻接表存储结构。若G G无回路，无回路，/则输出则输出G G的顶点的的顶点的1 1个拓扑序列并返回个拓扑序列并返回OKOK，否则，否则ERRORERROR FindInDegree(GFindInDegree(G，indegree)indegree)；/对各顶点求入度对各顶点求入度indegree0.vernum-1indegree0.vernum-1 InitStack(S)InitStack(S)；for(i=0for(i=0
13、；+i+i)/)/建零入度顶点栈建零入度顶点栈 if(!indegreei)Push(Sif(!indegreei)Push(S，i)i)/入度为入度为0 0者进栈者进栈 count=0count=0；/对输出顶点计数对输出顶点计数while(!StackEmpty(S)while(!StackEmpty(S)Pop(SPop(S，i);i);printf(iprintf(i，G.verticesi.data);+count;G.verticesi.data);+count;/输出输出i i号顶点并计数号顶点并计数 for(p=G.verticesi.firstarc;p;p=p-nextar
14、c)for(p=G.verticesi.firstarc;p;p=p-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；/Topol
15、ogicalSort/TopologicalSort 分析：分析：对有对有 n n 个顶点和个顶点和 e e 条弧的有向图而言，建条弧的有向图而言，建立求各顶点的入度的时间复杂度为立求各顶点的入度的时间复杂度为O(e)O(e)；建零入；建零入度顶点栈的时间复杂度为度顶点栈的时间复杂度为O(n)O(n)；在拓扑排序过程；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈，出一中，若有向图无环，则每个顶点进一次栈，出一次栈，入度减次栈，入度减1 1的操作在的操作在 WHILEWHILE语句中总共执行语句中总共执行e e次，所以，总的时间复杂度为次，所以，总的时间复杂度为O(n+e)O(n+e)。拓扑排序的算法是下一讲讨论的求关键路径的拓扑排序的算法是下一讲讨论的求关键路径的基础。基础。