数据结构有向无环图及其应用分析.ppt

三、关键路径 1.实例： v1 0 v2 1 v3 2 v4 3 v5 4 v6 5 v7 6 v8 7 v9 8 a1=6 a4=1 a2=4 a3=5 a5=1 a6=2 a7=9 a11=4 a10=2 a8=7 a9=4 ⑧求关键路径的算法思想： 1）设ve(0)=0；按拓扑顺序利用如下公式依次求其余各顶点j(j=1,2,...n-1)的ve(j): 2）设vl(n-1)=ve(n-1)；按拓扑逆顺序利用如下公式依次求其余各顶点j(j=n-2,...,2,1,0)的vl(j): i j dut(i,j) vl(i)=Min{vl(j)-dut(i,j)} j ve(j)=Max{ve(i)+dut(i,j)} i * * 有向无环图及其应用 一、定义 一个无环的有向图称为有向无环图，简写为DAG（directed acycline graph）。 与有向二叉树相比，有向无环图是更一般的特殊有向图。 实例： 有向树 有向无环图 有向图 教材179页给出了有向无环图的一个简单应用： 用有向无环图描述算术表达式。 二、拓扑排序 1.引例：现有计算机课程12门，如下表所示： c9,c10,c1 数值分析 c12 c9 普通物理 c11 c9 线性代数 c10 无 高等数学 c9 c3,c6 操作系统 c8 c5,c3 编译原理 c7 c11 计算机组成原理 c6 c3,c4 语言的设计和分析 c5 c1 汇编语言 c4 c1,c2 数据结构 c3 c1 离散数学 c2 无 程序设计基础 c1 先修课程 课程名称 课程编号 c1 c9 c4 c2 c12 c10 c11 c3 c5 c6 c7 c8 二、拓扑排序 c1 c9 c4 c2 c12 c10 c11 c3 c5 c6 c7 c8 2.拓扑排序： 偏序是指集合中仅有部分元素可比较大小(或先后)； 全序是指集合中所有元素均可比较大小（或先后）。 二、拓扑排序 c1 c9 c4 c2 c12 c10 c11 c3 c5 c6 c7 c8 2.拓扑排序： 拓扑排序是指将一个偏序关系转化为全序关系的过程的特殊操作。 二、拓扑排序 c1 c9 c4 c2 c12 c10 c11 c3 c5 c6 c7 c8 3.方法： ①在有向图中选择一个没有前驱（即入度为0）的顶点并输出之。 ②在有向图中删除刚刚输出的顶点及所有以该顶点为尾的弧。 ③图中若不再有入度为0的顶点，则结束；否则转①。 二、拓扑排序 c1 c9 c4 c2 c12 c10 c11 c3 c5 c6 c7 c8 3.方法： c1 拓扑序列： c2 c3 c4 c5 c7 c9 c10 c11 c6 c12 c8 二、拓扑排序 3.方法： c1 拓扑序列： c2 c3 c4 c5 c7 c9 c10 c11 c6 c12 c8 注意1：从某种意义下来说，拓扑排序的结果是不唯一的。 注意2：这种以顶点表示活动的有向无环图称为活动在顶点的网，简称AOV(Activity On Vertex Network)网。 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices[0] v1 3 2 ^ 1 G.vertices[1] ^ v2 G.vertices[2] v3 4 ^ 1 G.vertices[3] v4 ^ 4 G.vertices[4] ^ v5 G.vertices[5] v6 4 ^ 3 data firstarc adjvex nextarc 另外增设一个存放各顶点的入度值的一维数组indegree: indegree[0..5] 0 3 2 1 2 0 0 1 2 3 4 5 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices[0] v1 3 2 ^ 1 G.vertices[1] ^ v2 G.vertices[2] v3 4 ^ 1 G.vertices[3] v4 ^ 4 G.vertices[4] ^ v5 G.vertices[5] v6 4 ^ 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree[0..5] 0 3 2 1 2 0 0 1 2 3 4 5 求indegree一维数组初值的程序： FindInDegree(ALGraph G,indegree[0..G.vexnum-1]{