华中科技大学：《数据结构》课程教学资源（PPT课件讲稿）第七章 图 Graph 7.5 有向无环图及其应用 7.6 最短路径

数结 华中科技大学 计犷机学院(9 9008=8799

2001 -- 12 -- 27/29 华中科技大学 数据结构计算机学院(9)

7.5有向无环图及其应用 个无环的有向图称为有向无环图( directed acycline graph) 简称DAG图 6B8 E 46 图1 图2 图3(非DAG)

7.5 有向无环图及其应用 一个无环的有向图称为有向无环图（directed acycline graph), 简称DAG图。 A D C B E F B A D E F C 6 8 5 7 4 6 2 C A D E B F 图1 图2 图3（非DAG）

7.5.1拓扑排序 AOVP (Activity On Vertex network) 以顶点表示活动,弧表示活动之间的优先关系的DAG图。 课程编号 课程名称 先决条件 CI 程序设计基础 无 C2 离散数学 CI 计算机软件专业课程 C3 数据结构 C1,C2 C4 汇编语言 C1 C5 语言的设计和分析 C3,C4 计算机原理 C7 编译原理 C5,C3 c8 操作系统 C3,C6 C9 高等数学 无 C10 线性代数 C9 Cll 普通物理 C9 数值分析 C9,C10,C1

7.5.1 拓扑排序 AOV网（Activity On Vertex network）： 以顶点表示活动，弧表示活动之间的优先关系的DAG图。 课程编号 课程名称 先决条件 C1 程序设计基础 无 C2 离散数学 C1 C3 数据结构 C1，C2 C4 汇编语言 C1 C5 语言的设计和分析 C3，C4 C6 计算机原理 C11 C7 编译原理 C5，C3 C8 操作系统 C3，C6 C9 高等数学 无 C10 线性代数 C9 C11 普通物理 C9 C12 数值分析 C9，C10，C1 计 算 机 软 件 专 业 课 程

C4 表示课程间关系的有向图 C6 拓扑排序:是有向图的全部顶点的一个线性序列,该序列保持了 原有向图中各顶点间的相对次序。例: (C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8) (C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8)

C1 C2 C4 C5 C3 C7 C12 C9 C10 C11 C6 C8 表 示 课 程 间 关 系 的 有 向 图 拓扑排序:是有向图的全部顶点的一个线性序列，该序列保持了 原有向图中各顶点间的相对次序。例： （C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8) （C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8)

拓扑排序算法思想:重复下列操作,直到所有顶点输出完。 (1)在有向图中选一个没有前驱的顶点输出(选择入度为0的顶点) (2)从图中删除该顶点和所有以它为尾的弧(修改其它顶点入度)。 输出V6 输出V1 输出V4 输出V5 输出V2 输出V3

拓扑排序算法思想：重复下列操作，直到所有顶点输出完。 （1）在有向图中选一个没有前驱的顶点输出(选择入度为0的顶点)； （2）从图中删除该顶点和所有以它为尾的弧(修改其它顶点入度) 。 V1 V2 V4 V6 V5 V3 V1 V2 V4 V5 V3 V2 V4 V5 V3 V2 V5 V3 V2 V5 V5 输出V6 输出V1 输出V4 输出V2 输出V3 输出V5

有回路的有向图不存在拓扑排序。 Q 5V4 输出V1 输出V3 不能输出

V2 V6 V4 V3 V1 V5 V2 V6 V4 V3 V5 V2 V6 V5 V3 输出V1 输出V3 不能输出 有回路的有向图不存在拓扑排序

7.5.2关键路径 AOEp (Activity On Edge 是一个带权的有向无环图,其中以顶点表示事件,弧表 示活动,权表示活动持续的时间 当AOE网用来估算工程的完成时间时,只有一个开始点 (入度为0,称为源点)和一个完成点(出度为0,称为汇点) 2. d a7=9 a7 a5 a8-7 78al14 a6=2

7.5.2 关键路径 AOE网（Activity On Edge）： 是一个带权的有向无环图，其中以顶点表示事件，弧表 示活动，权表示活动持续的时间。 当AOE网用来估算工程的完成时间时，只有一个开始点 （入度为0,称为源点）和一个完成点（出度为0，称为汇点） V2 V1 V6 V3 V4 V5 V7 V8 V9

AOE网研究的问题: (1)完成整项工程至少需要多少时间; (2)哪些活动是影响工程进度的关键。 在AOE网中,部分活动可并行进行,所以完成工程的最 短时间是从开始点到完成点的最长路径长度。路径长度 最长的路径称为关键路径( Critical Path)

AOE网研究的问题： （1） 完成整项工程至少需要多少时间； （2） 哪些活动是影响工程进度的关键。 在AOE网中，部分活动可并行进行，所以完成工程的最 短时间是从开始点到完成点的最长路径长度。路径长度 最长的路径称为关键路径（Critical Path）

(顶点)事件v的最早发生时间ve(i): 从开始点到v的最长路径长度。(ve(v1)=0) 既表示事件vi的最早发生时间,也表示所有以ⅵi为尾的 弧所表示的活动ak的最早发生时间e(k)。(如下例的a7,a8) y2、 a a2=4 3a5=1 N5)8=7 了5 仅有一个前驱顶点: ve(v2)=ve(v1)+6=0+6=6 有多个前驱顶点: ve(v5)=max{ve(前驱顶点)+ ve(v3)=ve(v1)+4=0+6=4 前驱活动时间} ve(v4)=ve(v1)+6=0+5=5 =max{6+1,4+1,5+5}=10 完成点(汇点)的ve(vn)为工程完成所需要的时间

(顶点）事件vi的最早发生时间ve(i)： 从开始点到vi的最长路径长度。（ve(v1)=0） 既表示事件vi的最早发生时间，也表示所有以vi为尾的 弧所表示的活动ak的最早发生时间e(k)。(如下例的a7,a8) V2 V1 V3 V4 V5 仅有一个前驱顶点： ve(v2)=ve(v1)+6=0+6=6 ve(v3)=ve(v1)+4=0+6=4 ve(v4)=ve(v1)+6=0+5=5 有多个前驱顶点： ve(v5)=max{ve(前驱顶点)+ 前驱活动时间} =max{6+1,4+1,5+5}=10 完成点（汇点）的ve(vn)为工程完成所需要的时间

不推迟整个工程完成的前提下,(顶点)事件v允许的最迟 开始时间v1(i):完成点(汇点)vn的的最早发生时间ve(m) 减去wk到Ⅶn的最长路径长度。 (vn的的最早发生时间ve(n)等于最迟开始时间v1(n))。 仅有一个后继顶点: 假定工程18天完成(ve(v9)=18 a84 则:v1(v9)=18 1(v7)=vl(v9)-2=16 Ⅴl(v8)=v1(v9)-4=14 1(v6)=v1(v8)-4=10 有多个后继顶点: v1(v5)=min{vl(v7)-9,vl(v8)-4}=min{7,10}=7

不推迟整个工程完成的前提下, (顶点）事件vi允许的最迟 开始时间vl(i)： 完成点（汇点）vn的的最早发生时间ve(n) 减去vk到vn的最长路径长度。 （vn的的最早发生时间ve(n)等于最迟开始时间vl(n)）。 V6 V5 V7 V8 V9 仅有一个后继顶点： 假定工程18天完成(ve(v9)=18) 则： vl(v9)=18 vl(v7)= vl(v9)-2=16 vl(v8)= vl(v9)-4=14 vl(v6)= vl(v8)-4=10 有多个后继顶点： vl(v5)= min{vl(v7)-9, vl(v8)-4}=min{7,10}=7