《有向无环图的应用》PPT课件

《《有向无环图的应用》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径7.5有向无环图及其应用有向无环图(directedacyclinegraph)简称DAG图，是描述一项工程或系统的进行过程的有效工具。对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间。有向无环图的应用：拓扑排序关键路径在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：①先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；②子项目之间无次序要求，即两个子项目可以同时进行，互不影响。

2、我们用一种有向图来表示上述问题。在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这种有向图叫做顶点表示活动的网络(ActivityOnVertexNetwork)简称为AOV网。7.5.1拓扑排序课程编号课程名称先导课程编号C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5算法分析与设计C3，C4C6计算机组成原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1课程先后关系如图：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6

3、c7c8c2在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。此外，任何活动i不能以它自己作为自己的前驱或后继，这叫做反自反性。从前驱和后继的传递性和反自反性来看，AOV网中不能出现回路(有向环)，回路表示顶点之间的先后关系进入了死循环。判断AOV网是否有有向环的方法是对该AOV网进行拓扑排序，将AOV网中顶点排列成一个线性有序序列，若该线性序列中包含AOV网全部顶点，则AOV网无环，否则，AOV网中存在有向环，该AOV网所代表的工程是不可行的。何谓“拓扑排序”？拓扑序列：在AOV网中，若不存在回

4、路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列。拓扑排序由AOV网构造拓扑序列的过程叫拓扑排序。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称为它的拓扑序列。拓扑有序序列：（C1，C2，C3，C4，C5，C8，C9，C7，C6）（C2，C5，C1，C8，C3，C9，C4，C7，C6）如何进行拓扑排序？解决方法：1）从有向图中选取一个没有前驱的顶点，并输出之；2）从有向图中删去此顶点以及所有以它为尾的弧；3）重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。后一种情况说明有向图中存在环。如何在计算机中实现拓

5、扑排序呢？拓扑排序算法的实现为了实现拓扑排序的算法，对给定的有向图可采用邻接表作为它的存储结构。将每个链表的表头结点构成一个顺序表，各表头结点的Data域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得到。在拓扑排序过程中，凡入度为零的顶点即是没有前趋的顶点，可将其取出列入有序序列中，同时将该顶点从图中删除掉不再考虑。删去一个顶点时，所有它的直接后继顶点入度均减1，表示相应的有向边也被删除掉。设置一个堆栈，将已检验到的入度为零的顶点标号进栈，当再出现新的无前趋顶点时，也陆续将其进栈。每次选入度为零的顶点时，只要取栈顶顶点即可。4∧0∧04∧21003∧14∧AOV网络

6、的邻接表01234顶点的入度数组下标用邻接表存储AOV网络，拓扑排序算法描述：(1)把邻接表中所有入度为零的顶点进栈；(2)在栈不空时：①退栈并输出栈顶的顶点j；②在邻接表的第j个单链表中，查找顶点为j的所有直接后继顶点k，并将k的入度减1。若顶点k的入度为零，则顶点k进栈；③若栈空时输出的顶点个数不是n，则有向图中有环路，否则拓扑排序完毕。拓扑排序算法StatusTopologicalSort(ALGraphG){//有向图G采用邻接表存储结构。若G无回路，//则输出G的顶点的1个拓扑序列并返回OK，否则ERRORFindInDegree(G，indegree)；//对各顶点求入度in

7、degree[0..vernum-1]InitStack(S)；for(i=0；i