数据结构第13周.ppt

图（4） 学习内容 1 拓扑排序 P227 2 AOE网与关键路径 P229 拓扑排序 问题提出：学生选修课程问题，学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业。 例如：用顶点表示上一张课程表的课程，用有向弧表示先决条件，若课程i是课程j的先决条件，则图中有弧 i,j  拓扑排序 解决方案：定义一个AOV网，用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网 Activity On Vertex network ，简称AOV网。 拓扑排序：把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫拓扑排序。 拓扑排序的方法： 1在有向图中选一个没有前驱的顶点且输出之。 2从图中删除该顶点和所有以它为尾的弧。 3重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。 练习：拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 【解析】解题关键是弄清拓扑排序的步骤。 （1）在AOV网中，选一个没有前驱的结点且输出； （2）删除该顶点和以它为尾的弧； （3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】1）0132465 2）0123465 关键路径 问题提出：把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始。 解决方案：AOE网 Activity On Edge ，也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。 路径长度——路径上各活动持续时间之和 关键路径——路径长度最长的路径 Ve j ——表示事件Vj的最早发生时间 Vl j ——表示事件Vj的最迟发生时间 e i ——表示活动ai的最早开始时间 l i ——表示活动ai的最迟开始时间 l i -e i ——表示完成活动ai的时间余量 关键活动即为关键路径上的活动，也就是l i e i 的活动 求关键路径步骤 求Ve i 求Vl j 求e i 求l i 计算l i -e i 选择题 关键路径是（　　） A） AOE网中从源点到汇点的最长路径 B） AOE网中从源点到汇点的最短路径 C） AOV网中从源点到汇点的最长路径 D） AOV网中从源点到汇点的最短路径 练习：写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 解析： 1）求事件的最早发生时间ve j , 最晚发生时间vl j ; 2）最早发生时间从ve 0 开始按拓扑排序向前递推到ve 6 , 最晚发生时间从vl 6 按逆拓扑排序向后递推到vl 0 ; 3）计算e i ,l i ：设ai由弧 j,k 表示，持续时间记为dut j,k ，则有下式成立 e i ve j l i vl k -dut j,k 4）找出e i -l i 0的活动既是关键活动。 答案：关键路径为a0- a4- a6- a9 * 例 课程代号 课程名称 先修棵 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 无 C1 C1,C2 C1 C3,C4 C11 C3.C5 C3,C6 无 C9 C9 C1,C9,C10 程序设计基础 离散数学 数据结构 汇编语言 语言的设计和分析 计算机原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1 （1） C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2 （2） C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3 （3） C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3--C4 （4） C6 C8 C10 C11 C12 拓扑序列：C1--C2--C3--C4--C5--C7--C9 C6 C8 C11 C12 拓扑序列：C1--C2--C3--C4--C5--C7--C9 --C10 （8） C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3--C4--C5 （5） C6 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3--C4--C5--C7 （6） C6 C8 C12 拓扑序列：C1--C2--C3--C4--C5--C7--C9 --C10--C11 （9） C8 C