第五章图(五)

1、第八讲 图（下）浙江大学 陈 越6.7 拓扑排序例：计算机专业排课课程号C1课程名称程序设计基础预修课程无C2C3离散数学数据结构无C1, C2C1C3C7C12C4微积分（一）无C2C5C6C7C8C9微积分（二）线性代数算法分析与设计逻辑与计算机设计基础计算机组成C4C5C3无C8C8C4C13C9C5C10C11C6C14C15C10C11操作系统编译原理C7, C9C7, C9C12C13C14C15数据库计算理论计算机网络数值分析C7C2C10C6AOV (Activity On Vertex)网络算法课程号课程名称预修课程C1C2程序设计基础离散数学无无C1C3C7C12C3数据结

2、构C1, C2C2C4C5C6微积分（一）微积分（二）线性代数无C4C5C8C13C9C10C11C14C7算法分析与设计C3C8逻辑与计算机设计基础无C4C5C6C15C9计算机组成C8C10C11C12C13操作系统编译原理数据库计算理论C7, C9C7, C9C7C2C1C3C7C2C13C6C8C9C4C5C14C15计算机网络数值分析C10C6C11 C12 C10 C15C141.AOV网络 (Activity On Vertices) 可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动Vi 必须先于活动Vj 进行。这种有向图叫做顶点表示活动的AOV网络 (

3、Activity On Vertices)。 注：在AOV网络中不能出现有向回路, 即有向环。如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。检测有向环的方法构造AOV的拓扑序列。2.拓扑排序构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中, 则该网络中必定不会出现有向环。例如, 对学生选课工程图进行拓扑排序, 得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 ,

4、 C5 , C3 , C4 , C7 , C6C8C3C5C4C9C6C7C1C23.进行拓扑排序的方法 输入AOV网络。令 n 为顶点个数。 在AOV网络中选一个没有直接前驱的顶点, 并输出之; 从图中删去该顶点, 同时删去所有它发出的有向边; 重复以上 、步, 直到n 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或n 图中还有未输出的顶点, 但已跳出处理循环。说明图中还剩下一些顶点, 它们都有直接前驱。这时网络中必存在有向环。nnnV拓扑排序拓扑序：如果图中从V到W有一条有向路径，则V一定排在W之前。满足此条件的顶点序列称为一个拓扑序获得一个拓扑序的过程就是拓扑排序AOV如果有合理的

5、拓扑序，则必定是有向无环如果有合理的拓扑序，则必定是有向无环图（Directed Acyclic Graph, DAG）V必须在必须在V开始开始之前结束 可以用一个队列来实现这个特定存储，开始时将所有入度为0的顶点插入队列，当队列不为空时，取出一个顶点V并输出，然后将与V相邻的顶点入度减1.当产生新的入度为0的顶点时，将其插入队列。重复这一过程直到队列为空时算法终止。所要寻找的拓扑排序即为各顶点从队列取出的序列。V1V2V4V5V3V6V7V8V1V4顶点1、4入队V2V4V5V3V6V7V8V1V4顶点1出队，顶点2入队V2V2V5V3V6V7V8V1V4顶点4出队，顶点5入队V2V5V5V

6、3V6V7V8V1V4顶点2出队V2V5V3V6V7V8V1V4顶点5出队，顶点3、6入队V2V5V3V6V6V7V8V1V4顶点3出队V2V5V3V6V7V8V1V4顶点6出队，顶点7入队V2V5V3V6V7V8V1V4顶点7出队，顶点8入队V2V5V3V6V7V8V1V4顶点8出队V2V5V3V6V7V8表 拓扑排序过程列表顶点顶点入度变化（1：初始8：结束）12345678V100000000V210000000V332210000V400000000V511000000V611110000V722222100V822222110入队列V1V4V2V5V3V6V7V8出队列V1V4V2V

7、5V3V6V7V86.8 关键路径计算关键路径计算课本例题6.19，图中结点内大写字母A-H表示活动，字母右下角带括号的数字表示完成此活动所需的时间。分析图中活动时间可知，完成路径A、C、F、H上的各活动需要11个时间单位，这几个活动中任意一个的延迟都会延长整个工期，实际上这是一条“关键路径”。但活动B可以延迟3个时间单位，并不会影响整个整个工程的完成进度，相对于关键路径，包含活动B的路径是非关键路径。v 从源点到各个顶点, 以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。 完成不同路径的活动所需的时间虽然不同, 但只有各条路径上所有活动都完成了, 整个工程才算完成。v 因此

8、, 完成整个工程所需的时间取决于从源点到汇点的最长路径长度, 即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。 为了便于分析关键路径，将活动为顶点的AOV图转换为活动为边的AOE图，有向边表示任务或活动，边上的权表示该活动持续的时间。在AOE图中顶点表示事件，每个事件对应一个活动及与之相关的其他活动完成。 如果一个活动是在几个活动完成后才能开始，则需要增加虚构的边和结点，来表示活动之间的这种依赖关系。 与AOV网相对应的是AOE(Activity On Edge) ，是边表示活动的有向无环图，如图所示。图中顶点表示事件(Event)，每

9、个事件表示在其前的所有活动已经完成，其后的活动可以开始；弧表示活动，弧上的权值表示相应活动所需的时间或费用。065432178a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2图图 一个一个AOE网网顶点1和10分别表示工程的开始和完成事件。活动D是在活动A和B都完成才能开始。A和B两个活动的完成表示为2和3两个事件，在两个事件中引入虚构结点6(灰色表示）和两条0标识（该活动所需时间为0）的虚构活动边，使得活动D是在A、B完成后才能开始。121036A/3B/2004567878109C/400E/1D/20G/2F/3k/4000H

10、/10用以下方法简化：对出度为1的顶点，如果其出边的权值为0，则可删除该顶点及其出边,该顶点的入边直接指向后面的顶点。12934A/3B/200567810C/40E/1D/20G/2F/3k/4H/10在各顶点的上方标出各事件最早完成的时间，在结束事件上方标出的11个时间单位是整个工程的最早完成时间。若Earliesti表示结点i的最早完成时间，Cv,w表示边的权值，则有：Earliest1=0Earliestw=max(Earliestv+Cv,w) E12934A/3B/200567810C/40E/1D/20G/2F/3k/4H/10032335751011还可求解每一事件i在不影响整

11、个工程完成情况下所允许最晚完成时间Latesti。计算是从结束事件开始，设结束顶点为事件n，按事件拓扑的相反次序逐个顶点结算，直到工程的初始顶点为止。Latestn=EarliestnLatestv=min(Latestw-Cv,w) E12934A/3B/200567810C/40E/1D/20G/2F/3k/4H/10055367781011各顶点的最早和最晚完成时间求出后，就可确定在不影响工程进度的前提下，每一活动最多能耽误的时间长短。这个时间是否为0决定了该活动是否处于关键路径上。求边上的允许耽误的最大时间Delayv,w采用的计算公式为:Delayv,w=Latestw-Earliestv-Cv,w12934A/3B/200567810C/40E/1D/20G/2F/3k/4H/10055367781011最多能耽误时间为0（即不允许有时间耽误）的活动都是“关键活动”，由关键活动构成的从头至尾的