图的应用 7.5有向无环图及其应用 7.5.1拓扑排序 7.5.2关键路径 7.6最短路径 7.6.1从某个源点到其余各顶点的最短路径 7.6.2每一对顶点间的最短路径
图的应用 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.5.2 关键路径 7.6 最短路径 • 7.6.1 从某个源点到其余各顶点的最短路径 • 7.6.2 每一对顶点间的最短路径
7.5有向无环图及其应用 个无环的有向图叫做有向无环图 简称DAG图 判断有向图中是否存在环的方法 有向树 DAG图 有向图
7.5 有向无环图及其应用 一个无环的有向图叫做有向无环图, 简称DAG图 判断有向图中是否存在环的方法 有向树 DAG图 有向图
有向无环图是 描述含有公共子式的表达式的有效工具 (a+b)*(b*(C+d)十(C+d)*e)*(C+d)*e) ⑥b 用二叉树描述表达式 用DAG描述表达式
有向无环图是 描述含有公共子式的表达式的有效工具. ((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e) * * * * * + + + + + a b b c c c d d d 用二叉树描述表达式 e e * * * * + + + a b b c d 用DAG描述表达式 e
有向无环图也是 描述一项工程或系统的进行过程的有效工具 编号课程名称预修课 C1程序设计基础无 C2离散数学 C3数据结构C1C2 C4汇编语言 C5语言设计分析C3C4 C6计算机原理c1l C7编译原理 C5. C3 C12 C8操作系统 C3 C6 C9高等数学无 (CoC C C10线性代数 C9 Cll普通物理C9 C12数值分析CC9cl0
有向无环图也是 描述一项工程或系统的进行过程的有效工具 编号 课程名称 预修课 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 数值分析 C1C9C10 C12 C10 C11 C9 C1 C2 C3 C4 C6 C5 C7 C8
7.5.1拓扑排序 AOV-kXX (Activity On Vertex) 口顶点一一活动 0弧一一活动间的优先关系 AOV一网不应该出现有向环 上例的拓扑排序序列之一: C1,C9,C2C4,C10,C1l,C3,C12,C6,C5,C7,C8
7.5.1 拓扑排序 AOV-网(Activity On Vertex) 顶点－－活动 弧－－活动间的优先关系 AOV－网不应该出现有向环 上例的拓扑排序序列之一： C1,C9, C2,C4,C10,C11, C3,C12,C6,C5, C7,C8