图定义术语章作业课件chap7-2014.pptx

17.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第七章图

27.5有向无环图及其应用

7.5.1拓扑排序

7.5.2关键路径

37.5有向无环图及其应用一个无环的有向图叫做有向无环图,简称DAG(directedacyclinegraph)图有向树DAG图有向图

4有向无环图是描述含有公共子式的表达式的有效工具.((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)*****+++++abbcccddd用二叉树描述表达式ee****+++abbcd用DAG描述表达式e

5有向无环图也是描述一项工程或系统的进行过程的有效工具.几乎所有的工程都可分为若干个称做活动的子工程，而这些子工程之间，通常受着一定条件的约束，如某些子工程的开始必须在另一些子工程完成之后，对整个工程和系统，人们关心的是两个方面的问题：一、工程能否顺利进行；二、估算整个工程所必须完成的最短时间。对应于有向图，即为进行拓扑排序和求关键路径的操作。

67.5.1拓扑排序（TopologicalSort）一个较大的工程往往被划分成许多子工程（称为活动），在整个工程中，有些子工程（活动）必须在其他有关子工程完成之后才能开始，即一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。对于整个工程和系统，人们关心工程是否能顺利进行。

7为了形象地反映出整个工程中各个子工程（活动）之间的先后关系，可用一个有向图来表示。用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网(ActivityOnVertexNetwork)，简称为AOV-网。

8a1a5a4a6a2a3a8a7a9课程安排PascalDSCompilerOSC施工从活动a1、a2开始，到达活动a8和a9时，整个施工结束。有向图中，顶点表示活动，弧ai，aj表示活动ai优先于活动aj。

9一个AOV网应该是一个有向无环图，因为若带有回路，则回路上的所有活动都无法进行。在AOV网中,若不存在回路,则所有活动可排列成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,我们把此序列叫做拓扑序列（不唯一）,由AOV网构造拓扑序列的过程叫做拓扑排序。拓扑排序是一种对非线性结构的有向图进行线性化的重要手段。AOV网可解决如下两个问题：（1）判定工程的可行性。显然，有回路，整个工程就无法结束（2）确定各项活动在整个工程执行中的先后顺序。

课程关系

11例如：对于下列有向图BDAC可求得拓扑有序序列：ABCD或ACBD

12BDAC反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}

13如图有如下拓扑有序序列：a1a2a3a4a6a5a7a8a9a2a6a1a3a4a5a7a9a8a1a5a4a6a2a3a8a7a9

14由AOV网构造拓扑序列的过程叫做拓扑排序，其基本思想为：从有向图中选一个无前驱的顶点输出；将此顶点和以它为起点的弧删除；重复1、2，直到不存在无前驱的顶点；若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的序列即为一个拓扑序列。

15abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念没有前驱的顶点??入度为零的顶点删除顶点及以它为尾的弧??弧头顶点的入度减1

16由于有向图的存储形式的不同，拓扑排序算法的实现也不同。(1)基于邻接矩阵表示的存储结构A为有向图G的邻接矩阵，则有：找图G中无前驱的顶点——在A中找到值全为0的列i；删除以i为起点的所有弧——将矩阵中i对应的行中各元素全部置为0。

17算法步骤如下：取1作为第1新序号(序号实际上是作计数器使用)。找一个未经编号的、值全为0的列j，若找到则转3；否则，若所有的列全部都编过号，拓扑排序结束，若有列未曾被编号，则该图中有回路。输出列号对应的顶点j，把新序号赋给所找到的列。将矩阵中j对应的行的各个元素全部置为0。新序号加1，转2。

18(2)基于邻接表的存储结构入度为零的顶点即