第16讲拓扑排序与关键路径详解.ppt

第十六讲 拓扑排序与关键路径 主讲：朱郑州 主要内容 AOV网 AOV网 拓扑排序 拓扑排序 拓扑排序 拓扑排序 拓扑排序 拓扑排序 拓扑排序 拓扑排序 拓扑排序 主要内容 AOE网 AOE网 AOE网 关键路径 首先计算以下与关键活动有关的量： 关键路径 关键路径 关键路径 关键路径 关键路径 关键路径 《数据结构》 Data Structure * 《数据结构》 Data Structure 1. 拓扑排序 2. 关键路径 AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。 什么是工程？工程有什么共性？ AOV网中出现回路意味着什么？ AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。 2.AOV网中不能出现回路 。 AOV网特点： 1.AOV网中的弧表示活动之间存在的某种制约关系。 什么是工程？工程有什么共性？ C4，C5，C6 数据库原理 C7 C2，C4 计算机原理 C6 C3，C4 数据结构 C5 C1, C2 程序设计 C4 C1 离散数学 C3 无 计算机导论 C2 无 高等数学 C1 先修课 课程名称 编号 C1 C2 C3 C4 C6 C5 C7 AOV网 拓扑序列：设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, …, vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。 拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序 。 拓扑序列使得AOV网中所有应存在的前驱和后继关系都能得到满足。 拓扑排序 基本思想： ⑴ 从AOV网中选择一个没有前驱的顶点并且输出； ⑵ 从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧； ⑶ 重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。 拓扑排序的结果？ 拓扑排序 C1 C2 C3 C4 C6 C5 C7 拓扑序列： C1, C2, C3, C4, C5, C6, C7 C1 C2 C3 C4 C6 C5 拓扑序列： C1, C2, C3, 说明AOV网中存在回路。 设计数据结构 1. 图的存储结构：采用邻接表存储 ，在顶点表中增加一个入度域。 顶点表结点 in vertex firstedge 2. 栈S：存储所有无前驱的顶点。 拓扑排序 (a) 一个AOV网 (b) AOV网的邻接表存储 0 1 2 3 4 5 in vertex firstedge 3 A ∧ 0 B 1 C 3 D 0 E 2 F ∧ 0 3 ∧ 0 0 5 ∧ 2 3 ∧ 3 5 ∧ A B C D E F 0 1 2 3 4 5 in vertex firstedge 3 A ∧ 0 B 1 C 3 D 0 E 2 F ∧ 0 3 ∧ 0 0 5 ∧ 2 3 ∧ 3 5 ∧ A B C D E F B E 0 1 2 3 4 5 in vertex firstedge 3 A ∧ 0 B 1 C 3 D 0 E 2 F ∧ 0 3 ∧ 0 0 5 ∧ 2 3 ∧ 3 5 ∧ A B C D E F B E 0 C 2 1 0 1 2 3 4 5 in vertex firstedge 3 A ∧ 0 B 0 C 2 D 0 E 1 F ∧ 0 3 ∧ 0 0 5 ∧ 2 3 ∧ 3 5 ∧ A B C D F B C 2 1 0 1 2 3 4 5 in vertex firstedge 2 A ∧ 0 B 0 C 1 D 0 E 1 F ∧ 0 3 ∧ 0 0 5 ∧ 2 3 ∧ 3 5 ∧ A B D F B D 0 1 0