有向无环图及其应用

有向无环图及其应用Tag内容描述：<p>1、有向无环图 及其应用 一、定义 一个无环的有向图称为有向无环图，简写为 DAG（directed acycline graph）。 与有向二叉树相比，有向无环图是更一般的特 殊有向图。 实例： 有向树 有向无环图有向图 教材179页给出了有向无环图的一个简单应用： 用有向无环图描述算术表达式。 二、拓扑排序 1.引例：现有计算机课程12门，如下表所示： 课程编号课程名称先修课程 c1程序设计基础无 c2离散数学c1 c3数据结构c1,c2 c4汇编语言c1 c5语言的设计和分析c3,c4 c6计算机组成原理c11 c7编译原理c5,c3 c8操作系统c3,c6 c9高等数学无 c10线性代数c9 c11。</p><p>2、有向无环图,无环的有向图称为有向无环图，简称DAG图 P179 图7.21：有向树、DAG图、有向图 DAG图可用于： 描述含有公共子式的表达式； 描述工程的进行过程； 有向无环图是描述一项工程进行过程的有效工具，主要进行拓扑排序和关键路径的操作。 工程能否顺利进行拓扑排序 完成整个工程所需的最短时间关键路径,活动网络 (Activity Network),计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都可以将工程分为若干个称作“活动”的子工程，完成了这些活动，整个工程就可以完成了。 例：计算机专业学生的学习就是一个。</p><p>3、7.5 有向无环图及应用,7.5.1 拓扑排序,用顶点边表示活动的网络，简称 AOV网络 (Activity On Vertices) 顶点：一个工程中的活动(Activity) 边：活动的顶点间的优先关系(Relation) 要解决的问题是： 将各个顶点 （代表各个活动）排列成一个线性有序 的序列，使得AOV网络中所有应存在的前驱和后继关系 都能得到满足。,课程代号 课程名 先修课程 C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C2 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C1 C9 计。</p><p>4、6.6 拓扑排序,用顶点边表示活动的网络，简称 AOV网络 (Activity On Vertices) 顶点：一个工程中的活动(Activity) 边：活动的顶点间的优先关系(Relation) 要解决的问题是： 将各个顶点 （代表各个活动）排列成一个线性有序 的序列，使得AOV网络中所有应存在的前驱和后继关系 都能得到满足。,课程代号 课程名 先修课程 C1 高等数。</p>