数据结构有向无环图及其应用.pptx
一、定义 一个无环的有向图称为有向无环图，简写为DAG（directed acycline graph）。与有向二叉树相比，有向无环图是更一般的特殊有向图。实例：有向树有向无环图有向图 教材179页给出了有向无环图的一个简单应用：用有向无环图描述算术表达式。第1页/共36页二、拓扑排序1.引例：现有计算机课程12门，如下表所示：课程编号课程名称先修课程c1程序设计基础无c2离散数学c1c3数据结构c1,c2c4汇编语言c1c5语言的设计和分析c3,c4c6计算机组成原理c11c7编译原理c5,c3c8操作系统c3,c6c9高等数学无c10线性代数c9c11普通物理c9c12数值分析c9,c10,c1c1c9c4c2c12c10c11c3c5c6c7c8第2页/共36页二、拓扑排序c1c9c4c2c12c10c11c3c5c6c7c82.拓扑排序：偏序是指集合中仅有部分元素可比较大小(或先后)；全序是指集合中所有元素均可比较大小（或先后）。第3页/共36页二、拓扑排序c1c9c4c2c12c10c11c3c5c6c7c82.拓扑排序：拓扑排序是指将一个偏序关系转化为全序关系的过程的特殊操作。第4页/共36页二、拓扑排序c1c9c4c2c12c10c11c3c5c6c7c83.方法：在有向图中选择一个没有前驱（即入度为0）的顶点并输出之。在有向图中删除刚刚输出的顶点及所有以该顶点为尾的弧。图中若不再有入度为0的顶点，则结束；否则转。第5页/共36页二、拓扑排序c1c9c4c2c12c10c11c3c5c6c7c83.方法：c1拓扑序列：c2 c3 c4 c5 c7 c9 c10 c11 c6 c12 c8第6页/共36页二、拓扑排序3.方法：c1拓扑序列：c2 c3 c4 c5 c7 c9 c10 c11 c6 c12 c8注意1：从某种意义下来说，拓扑排序的结果是不唯一的。注意2：这种以顶点表示活动的有向无环图称为活动在顶点的网，简称AOV(Activity On Vertex Network)网。第7页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643datafirstarcadjvex nextarc另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5021230 0 1 2 3 4 5第8页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5021230 0 1 2 3 4 5求indegree一维数组初值的程序：FindInDegree(ALGraph G,indegree0.G.vexnum-1 for(i=0;iadjvex;+indegreek;p=p-nextarc;/FindInDegree第9页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5021230 0 1 2 3 4 5拓扑排序算法思想：设一个栈S，入度为0的顶点的序号进栈。如0，5 进栈。count=0(打印顶点个数计数器)。当栈S不空时，出栈一个元素并打印相应顶点；count加1。该顶点的所有邻接点的入度减1，减1后入度为0的顶点的序号进栈。重复第二步，直至栈空时转。若count=G.vexnum,则拓扑排序成功；否则图中必有环路，拓扑排序失败。第10页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5021230 0 1 2 3 4 550s第11页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5021230 0 1 2 3 4 50s5打印G.vertices5.data4号和3号顶点的入度分别减1第12页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5021120 0 1 2 3 4 50s第13页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5021120 0 1 2 3 4 5 s0打印G.vertices0.data3号、2号、1号顶点的入度分别减1第14页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5010020 0 1 2 3 4 523s第15页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5010020 0 1 2 3 4 523s第16页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5010020 0 1 2 3 4 5 3s2打印G.vertices2.data4号、1号顶点的入度分别减1第17页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5000010 0 1 2 3 4 513s第18页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5000010 0 1 2 3 4 5 3s1打印G.vertices1.data第19页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5000010 0 1 2 3 4 5 3s第20页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5000010 0 1 2 3 4 5 s3打印G.vertices3.data4号顶点的入度减1第21页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5000000 0 1 2 3 4 5 4s第22页/共36页二、拓扑排序4.算法说明：为了使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放各顶点的入度值的一维数组indegree:indegree0.5000000 0 1 2 3 4 5 s4打印G.vertices4.data最后输出的拓扑序列为：v6v1v3v2v4v5第23页/共36页二、拓扑排序4.程序：Status TopologicalSort(ALGraph)FindIndegree(G,indegree);InitStack(S);for(i=0;iG.vexnum;+i)if (!indegreei)Push(S,i);/入度为0的顶点的序号进栈 count=0;while(!StackEmpty(S)Pop(S,i);couti nextarc)第24页/共36页Status TopologicalSort(ALGraph)FindIndegree(G,indegree);InitStack(S);for(i=0;iG.vexnum;+i)if (!indegreei)Push(S,i);/入度为0的顶点的序号进栈 count=0;while(!StackEmpty(S)Pop(S,i);couti nextarc)k=p-adjvex;-indegreek;if(!(indegreek)Push(S,k);第25页/共36页Status TopologicalSort(ALGraph)FindIndegree(G,indegree);InitStack(S);for(i=0;iG.vexnum;+i)if (!indegreei)Push(S,i);/入度为0的顶点的序号进栈 count=0;while(!StackEmpty(S)Pop(S,i);couti nextarc)k=p-adjvex;-indegreek;if(!(indegreek)Push(S,k);/while if (count=G.vexnum)return OK;else return ERROR;/TopologicalSort第26页/共36页Status TopologicalSort(ALGraph)FindIndegree(G,indegree);InitStack(S);for(i=0;iG.vexnum;+i)if (!indegreei)Push(S,i);/入度为0的顶点的序号进栈 count=0;while(!StackEmpty(S)Pop(S,i);couti nextarc)k=p-adjvex;-indegreek;if(!(indegreek)Push(S,k);/while if (count=G.vexnum)return OK;else return ERROR;/TopologicalSort第27页/共36页三、关键路径1.实例：v10v21v32v43v54v65v76v87v98a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a10=2a8=7a9=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第28页/共36页三、关键路径1.实例：v10v21v32v43v54v65v76v87v98a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a10=2a8=7a9=4活动ai和它所依附的顶点的关系：设有：jkai=dut()则有：1.e(i)=ve(j)2.l(i)=vl(k)-dut()即：活动ai的最早开始时间等于事件j的最早开始时间；活动ai的最迟开始时间等于事件k的最迟开始时间减活动ai的持续时间。第29页/共36页三、关键路径1.实例：v10v21v32v43v54v65v76v87v98a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a10=2a8=7a9=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):ijdut()vl(i)=Minvl(j)-dut()jve(j)=Maxve(i)+dut()i第30页/共36页三、关键路径1.实例：v10v21v32v43v54v65v76v87v98a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a10=2a8=7a9=4例如：求上例各顶点的最早开始时间和最迟开始时间：i012345678备注备注顶点顶点vv1v2v3v4v5v6v7v8v9最早发生时间最早发生时间ve(i)最迟发生时间最迟发生时间vl(i)0645771614181814161078660第31页/共36页三、关键路径1.实例：v10v21v32v43v54v65v76v87v98a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a10=2a8=7a9=4例如：求上例各顶点的最早开始时间和最迟开始时间：i012345678备注备注顶点顶点vv1v2v3v4v5v6v7v8v9最早发生时间最早发生时间ve(i)最迟发生时间最迟发生时间vl(i)0645771614181814161078660其中：v1,v2,v5,v7,v8,v9为关键活动。第32页/共36页作业：1.试分析下面有向图的矩阵存储结构和邻接表存储结构：abcd12342.试编写函数，求在无向图的邻接表类的对象G中各顶点vi的度。3.试编写函数，在无向图的邻接表类的对象G中判断两个顶点vi和vj之间是否存在一条从vi到vj的路径（提示：利用深度或广度优先遍历函数）。第33页/共36页作业：4.自己任意设计画出一个AOV网（即画出一个有向无环图，要求有8个以上的顶点），然后试着写出它的一个拓扑序列。5.自己任意设计画出一个AOE网（即画出一个有向无环图，且边上有权值，要求有10个以上的顶点），然后试着写出各顶点的最早开始时间和最迟开始时间，并写出该图的若干条关键路径。第34页/共36页End第35页/共36页感谢您的观看！第36页/共36页
