数结 华中科技大学 计犷机学院(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