有向无环图及其应用ppt课件

《有向无环图及其应用ppt课件》由会员分享，可在线阅读，更多相关《有向无环图及其应用ppt课件（23页珍藏版）》请在金锄头文库上搜索。

1、有向无环图无无环的有向的有向图称称为有向无有向无环图，简称称DAGDAG图P179 P179 图7.217.21：有向：有向树、DAGDAG图、有向、有向图DAGDAG图可用于：可用于： 描画含有公共子式的表达式；描画含有公共子式的表达式； 描画工程的描画工程的进展展过程；程；有向无有向无环图是描画一是描画一项工程工程进展展过程的有程的有效工具，主要效工具，主要进展拓扑排序和关展拓扑排序和关键途径的途径的操作。操作。 工程能否工程能否顺利利进展展拓扑排序拓扑排序 完成整个工程所需的最短完成整个工程所需的最短时间关关键途途径径活动网络 (Activity Network)n n方案、施工方案、施

2、工过程、消程、消费流程、程序流程等都流程、程序流程等都是是“工程。除了很小的工程外，普通都可以工程。除了很小的工程外，普通都可以将工程分将工程分为假假设干个称作干个称作“活活动的子工程，的子工程，完成了完成了这些活些活动，整个工程就可以完成了。，整个工程就可以完成了。n n例：例：计算机算机专业学生的学学生的学习就是一个工程，就是一个工程，每一每一门课程的学程的学习就是整个工程的一个活就是整个工程的一个活动，其中有些其中有些课程要求先修程要求先修课程，有些那么不要程，有些那么不要求，求，这样在有的在有的课程之程之间就存在就存在领先关系，先关系，而有的而有的课程那么可以并行学程那么可以并行学习。

3、用用顶点表示活点表示活动的网的网 (AOV-网网) C1 高等数学高等数学 C2 程序程序设计设计根底根底 C3 离散数学离散数学 C1, C2 C4 数据构造数据构造 C3, C2 C5 高高级级言言语语程序程序设计设计 C2 C6 编译编译原理原理 C5, C4 C7 操作系操作系统统 C4, C9 C8 大学物理大学物理 C1 C9 计计算机原理算机原理 C8 课程代号程代号课程称号程称号先修先修课程程学生课程学习工程图学生课程学习工程图C8C3C5C4C9C6C7C1C2n n可以用有向可以用有向图表示一个工程。在表示一个工程。在这种有向种有向图中，用中，用顶点表示活点表示活动，用有向

4、，用有向边表示活表示活动Vi 必需先于活必需先于活动Vj 进展。展。这种有种有向向图称作称作顶点表示活点表示活动的的AOV网网 (Activity On Vertex)。 n n在在AOV网网络中不能出中不能出现有向回路有向回路, 即有向即有向环。假。假设出出现了有向了有向环，那么意味着某，那么意味着某项活活动应以本人作以本人作为先决条件。先决条件。n n因此，因此，对给定的定的AOV网网络，必需先判，必需先判别它它能否存在有向能否存在有向环。n n检测有向有向环的一种方法是的一种方法是对AOV网网络构造构造它的拓扑有序序列。即将各个它的拓扑有序序列。即将各个顶点点 (代表各代表各个活个活动)

5、陈列成一个列成一个线性有序的序列，使得性有序的序列，使得AOV网网络中一切中一切应存在的前存在的前驱和后和后继关系关系都能得到都能得到满足。足。 n n这种构造种构造AOV网网络全部全部顶点的拓扑有序序点的拓扑有序序列的运算就叫做拓扑排序。列的运算就叫做拓扑排序。n n假假设经过拓扑排序能将拓扑排序能将AOV网网络的一切的一切顶点都排入一个拓扑有序的序列中点都排入一个拓扑有序的序列中, 那么那么该网网络中必定不会出中必定不会出现有向有向环。n n假假设AOV网网络中存在有向中存在有向环，此，此AOV网网络所代表的工程是不可行的。所代表的工程是不可行的。n n例如例如, 对学生学生课程学程学习工

6、程工程图进展拓扑排序展拓扑排序, 得到的拓扑有序序列得到的拓扑有序序列为n n C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6C8C3C5C4C9C6C7C1C2拓扑排序的方法拓扑排序的方法 输入入AOV网网络，令，令 n 为顶点个数。点个数。 在在AOV网网络中中选一个没有直接前一个没有直接前驱的的顶点点, 并并输出之出之; 从从图中中删去去该顶点点, 同同时删去一切它去一切它发出出的有向的有向边; 反复以上反复以上 、步步, 直到直到 全部全部顶点均已点均已输出，

7、拓扑有序序列构成，拓出，拓扑有序序列构成，拓扑排序完成；或扑排序完成；或 图中中还有未有未输出的出的顶点点, 但已跳出但已跳出处置循置循环。阐明明图中中还剩下一些剩下一些顶点点, 它它们都有直接前都有直接前驱。这时网网络中必存在有向中必存在有向环。C0C1C2C3C4C5拓扑排序的拓扑排序的过程程(a) 有向无环图有向无环图C2C5C1C0C3(b) 输出顶点输出顶点C4C1C2C5C3(c) 输出顶点输出顶点C0C4C0C2C5C1C3(d) 输出顶点输出顶点C3C1C2C5(e) 输出顶点输出顶点C2C5C1(f) 输出顶点输出顶点C1C5(g) 输出顶点输出顶点C5 最后得到的拓扑有序序

8、列最后得到的拓扑有序序列为 C4 , C0 , C3 , C2 , C1 , C5 。它。它满足足图中中给出的一切前出的一切前驱和后和后继关关系，系，对于本来没有于本来没有这种关系的种关系的顶点，如点，如C4和和C2，也排出了先后次序关系。，也排出了先后次序关系。(h) 拓扑排序完成拓扑排序完成AOV网网络及其及其邻接表表示接表表示C0C1C2C3C4C5 C0 C1 C2 C3 0 C4 C5 0012345indegree data adj 130103 1 dest link 3 0 5 1 5 0 0 1 5 0n n在在邻接接表表中中增增设一一个个数数组indegree ，记录各各顶

9、点点入入度度。入入度度为零零的的顶点点即即无无前前驱顶点。点。n n在在算算法法中中, 运运用用一一个个存存放放入入度度为零零的的顶点点的的栈, 供供选择和和输出无前出无前驱的的顶点。点。n n 拓扑排序算法可描画如下：拓扑排序算法可描画如下：建立入度建立入度为零的零的顶点点栈;当入度当入度为零的零的顶点点栈不空不空时, 反复反复执行行 从从顶点点栈中退出一个中退出一个顶点点, 并并输出之出之; 从从AOV网网络中中删去去这个个顶点和它点和它发出的出的边, 边的的终顶点入度减一点入度减一; 假假设边的的终顶点入度减至点入度减至0, 那么那么该顶点点进入入度度为零的零的顶点点栈; 假假设输出出顶

10、点个数少于点个数少于AOV网网络的的顶点个数点个数, 那么那么报告网告网络中存在有向中存在有向环。P182算法算法7.12用用边表表示示活活动的的网网络(AOE网网)n n假假设在在带权的有向无的有向无环图中中, 用有向用有向边表示表示一个工程中的活一个工程中的活动 (Activity), 用用边上上权值表示活表示活动继续时间 (Duration), 用用顶点表示点表示事件事件 (Event), 那么那么这样的有向的有向图叫做用叫做用边表示活表示活动的网的网络, 简称称 AOE ( Activity On Edges ) 网。网。n nAOE网在某些工程网在某些工程进度估算方面非常有用。度估算

11、方面非常有用。例如，可以使人例如，可以使人们了解：了解：n n完成整个工程至少需求多少完成整个工程至少需求多少时间(假假设网网络中没有中没有环)? uu为缩短完成工程所需的短完成工程所需的时间, 该当加快哪当加快哪些活些活动? uu从源点到各个从源点到各个顶点点, 以及从源点到以及从源点到汇点的点的有向途径能有向途径能够不止一条，不止一条，这些途径的些途径的长度度也能也能够不同，完成不同途径的活不同，完成不同途径的活动所需的所需的时间虽然不同，但只需各条途径上一切活然不同，但只需各条途径上一切活动都完成了都完成了, 整个工程才干完成。整个工程才干完成。uu因此因此, 完成整个工程所需的完成整个

12、工程所需的时间取决于从取决于从源点到源点到汇点的最点的最长途径途径长度度, 即在即在这条途条途径上一切活径上一切活动的的继续时间之和。之和。这条途径条途径长度最度最长的途径叫做关的途径叫做关键途径途径(Critical Path)。a9=61324a1=8a2=125678a10=12a8=18a5=28a6=8a7=6a3=14a4=10n n要找出关要找出关键途径，必需找出关途径，必需找出关键活活动, 即不即不按期完成就会影响整个工程完成的活按期完成就会影响整个工程完成的活动。n n关关键途径上的一切活途径上的一切活动都是关都是关键活活动。因。因此此, 只需找到了关只需找到了关键活活动,

13、就可以找到关就可以找到关键途径。例如途径。例如, 以下以下图就是一个就是一个AOE网。网。定定义几个与几个与计算关算关键活活动有关的量：有关的量： 事件事件Vi 的最早的最早发生生时间ve(i) 是从源点是从源点V0 到到顶点点Vi 的最的最长途径途径长度度 事件事件Vi 的最的最迟发生生时间vli 是是在在保保证汇点点Vn-1 在在ven-1 时辰辰完完成成即即不不影影响响整整个个工工程程工工期期的的前前提提下下，事事件件Vi 允允许的最的最迟开开场时间。 活活动ak 的最早能的最早能够开开场时间 ek 设活活动ak 在在弧弧上上, 那那么么ek是是从从源源点点V0到到顶点点Vi 的最的最长

14、途径途径长度。因此度。因此, ek = vei 活活动ak 的最的最迟允允许开开场时间 lk 在不会引起整个工程在不会引起整个工程时间延延误的前提下的前提下, 该活活动允允许的最的最迟开开场时间。 lk = vlj - dur()。 其中其中, dur()是完成是完成 ak 所需的所需的时间。 时间余量余量 lk - ek 表示活表示活动 ak 的最早能的最早能够开开场时间和最和最迟允允许开开场时间的的时间余量。余量。lk = ek 表示活表示活动 ak 是没有是没有时间余量的关余量的关键活活动。为找出关找出关键活活动, 需求求出各个活需求求出各个活动的的 ek 与与 lk，以判，以判别能否能

15、否 lk = ek。n n为求得求得 ek与与 lk, 需求先求得从源点需求先求得从源点 V0 到各到各个个顶点点 Vi 的的 vei 和和 vli。n n求求vei和和vli的的递推公式推公式n n 从从 ve0 = 0 开开场，向前，向前递推推n n S2, i = 1, 2, , n-1 n nS2 是一切指向是一切指向Vi 的有向的有向边的集合。的集合。n n 从从vln-1 = ven-1开开场，反向，反向递推推n n S1, i = n-2, n-3, , 0n nS1是一切源自是一切源自Vi的有向的有向边的集合。的集合。这这两个两个两个两个递递推公式的推公式的推公式的推公式的计计

16、算必需分算必需分算必需分算必需分别别在拓扑有序及逆拓扑有序的前提下在拓扑有序及逆拓扑有序的前提下在拓扑有序及逆拓扑有序的前提下在拓扑有序及逆拓扑有序的前提下进进展。展。展。展。设设活活活活动动ak (k=1,2,e)ak (k=1,2,e)在在在在带权带权有向有向有向有向边边 上上上上, , 其其其其继续时间继续时间用用用用dur () dur () 表示表示表示表示, , 那么有那么有那么有那么有 ek = vei ek = vei； lk = vlj - dur() lk = vlj - dur()；k = 1, 2, , ek = 1, 2, , e。这样这样就得到就得到就得到就得到计计

17、算关算关算关算关键键途径的算法。途径的算法。途径的算法。途径的算法。为为了了了了简简化算法化算法化算法化算法, , 假定在求关假定在求关假定在求关假定在求关键键途径之前曾途径之前曾途径之前曾途径之前曾经对经对各各各各顶顶点点点点实现实现了拓扑排序了拓扑排序了拓扑排序了拓扑排序, , 并按拓扑有序的并按拓扑有序的并按拓扑有序的并按拓扑有序的顺顺序序序序对对各各各各顶顶点重新点重新点重新点重新进进展了展了展了展了编编号。号。号。号。对算法算法7.12作如下修正得算法作如下修正得算法7.13： 算法算法7.13求各事件的求各事件的ve 设初初值ve(i)=0 (0 i n-1) 计算算Vj的直接后的

18、直接后继Vk的的ve(k)： 假假设ve(j)+dut() ve(k) 那么那么ve(k)=ve(j)+ dut() 为求求vl，设一一栈记录拓扑有序序列，之拓扑有序序列，之后后弹栈求逆拓扑有序序列求逆拓扑有序序列算法算法7.14 先求各事件的先求各事件的vl，再求各活，再求各活动的的e和和l7.14中用中用ee和和el表示，当某个活表示，当某个活动的的e=l，那么那么该活活动是关是关键活活动1324a1=8a2=125678a10=12a9=6a8=18a5=28a6=8a7=6a3=14a4=10VeVl1 2 3 4 5 6 7 8 0 8 12 22 28 40 46 58 0 8 1

19、2 22 28 40 46 58el0 0 8 12 12 22 22 28 40 460 0 8 12 12 32 22 28 40 461 2 3 4 5 6 7 8 9 10三条关三条关三条关三条关键键途径：途径：途径：途径：1-2-4-5-7-81-2-4-5-7-81-3-4-5-7-8 1-3-6-7-81-3-4-5-7-8 1-3-6-7-8留意留意一切一切顶点按拓扑有序的次序点按拓扑有序的次序编号号仅计算算 vei 和和 vli 是不是不够的，的，还须计算算 ek 和和 lk。不是任一关不是任一关键活活动加速一定能使整个工程加速一定能使整个工程提早。提早。想使整个工程提早，要思索各条关想使整个工程提早，要思索各条关键途径途径上一切关上一切关键活活动。