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

有向无环图 及其应用 一、定义 一个无环的有向图称为有向无环图，简写为 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普通物理c9 c12数值分析c9,c10,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.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 data firstarc adjvex nextarc 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 021230 0 1 2 3 4 5 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 021230 0 1 2 3 4 5 求indegree一维数组初值的程序： FindInDegree(ALGraph G,indegree0G.vexnum-1 for(i=0;iadjvex; +indegreek; p=p-nextarc; /FindInDegree 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 021230 0 1 2 3 4 5 拓扑排序算法思想： 设一个栈S，入度为0的顶点的序 号进栈。如0，5 进栈。count=0(打 印顶点个数计数器)。 当栈S不空时，出栈一个元素并 打印相应顶点；count加1。 该顶点的所有邻接点的入度减1， 减1后入度为0的顶点的序号进栈。 重复第二步，直至栈空时转。 若count=G.vexnum,则拓扑排序 成功；否则图中必有环路，拓扑排 序失败。 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 021230 0 1 2 3 4 5 5 0 s 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 021230 0 1 2 3 4 5 0 s 5 打印G.vertices5.data 4号和3号顶点 的入度分别减1 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 021120 0 1 2 3 4 5 0 s 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 021120 0 1 2 3 4 5 s 0 打印G.vertices0.data 3号、2号、1号顶 点的入度分别减1 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 010020 0 1 2 3 4 5 2 3 s 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 010020 0 1 2 3 4 5 2 3 s 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 010020 0 1 2 3 4 5 3 s 2 打印G.vertices2.data 4号、1号顶点的入 度分别减1 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 000010 0 1 2 3 4 5 1 3 s 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 000010 0 1 2 3 4 5 3 s 1 打印G.vertices1.data 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 000010 0 1 2 3 4 5 3 s 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 000010 0 1 2 3 4 5 s 3 打印G.vertices3.data 4号顶点的入度减1 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 000000 0 1 2 3 4 5 4 s 二、拓扑排序 4.算法说明：为了使说明过程简单起见，我们以下 图为例： v1 0 v2 1 v3 2 v4 3 v6 5 v5 4 G.vertices0 v1 3 2 1 G.vertices1 v2 G.vertices2 v3 4 1 G.vertices3 v4 4 G.vertices4 v5 G.vertices5 v6 4 3 另外增设一个存放各顶点的入度值的一维数组indegree: indegree05 000000 0 1 2 3 4 5 s 4 打印G.vertices4.data 最后输出的拓扑序列为：v6v1v3v2v4v5 二、拓扑排序 4.程序： Status TopologicalSort(ALGraph) FindIndegree(G,indegree); InitStack(S); for (i=0;inextarc) Status TopologicalSort(ALGraph) FindIndegree(G,indegree); InitStack(S); for (i=0;inextarc) k=p-adjvex; -indegreek; if (!(indegreek) Push(S,k) ; Status TopologicalSort(ALGraph) FindIndegree(G,indegree); InitStack(S); for (i=0;inextarc) k=p-adjvex; -indegreek; if (!(indegreek) Push(S,k) ; /while if (count= =G.vexnum) return OK; else return ERROR; /TopologicalSort Status TopologicalSort(ALGraph) FindIndegree(G,indegree); InitStack(S); for (i=0;inextarc) k=p-adjvex; -indegreek; if (!(indegreek) Push(S,k) ; /while if (count= =G.vexnum) return OK; else return ERROR; /TopologicalSort 三、关键路径 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 顶点vi表示事件； 弧既描述事件之间的依赖关系，又表示某种活动ai的持续时间； 从“起点”(v1)开始到“终点”(v9)的最长路径称为关键路径； 每个活动ai都有一个最早开始时间e(i)和一个最迟开始时间l(i)； 例如：对于a5，有： e(5)=4；l(5)=6 关键路径上的活动ai称为关键活动，一定满足：e(i)=l(i)； 每个事件v也有一个最早开始时间ve(k)和一个最迟开始时间vl(k); 例如：对于事件v3，有： ve(2)=4；vl(2)=6 三、关键路径 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 活动ai和它所依附的顶点的关系： 设有： j k ai=dut( ) 则有： 1. e(i)=ve(j) 2. l(i)=vl(k)-dut() 即：活动ai的最早开始时间等于事件j 的最早开始时间； 活动ai的最迟开始时间等于事件k的最 迟开始时间减活动ai的持续时间。 三、关键路径 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() vl(i)=Minvl(j)-dut() j ve(j)=Maxve(i)+dut() i 三、关键路径 1.实例： v1 0 v2 1 v3 2 v4 3 v5 4 v6 5 v7 6 v8