《数据结构有向无环图及其应用.ppt》由会员分享，可在线阅读，更多相关《数据结构有向无环图及其应用.ppt（36页珍藏版）》请在三一办公上搜索。
1、有向无环图及其应用,一、定义,一个无环的有向图称为有向无环图，简写为DAG（directed acycline graph）。与有向二叉树相比，有向无环图是更一般的特殊有向图。,实例：,有向树,有向无环图,有向图,教材179页给出了有向无环图的一个简单应用：用有向无环图描述算术表达式。,二、拓扑排序,1.引例：现有计算机课程12门，如下表所示：,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.拓扑排序：,偏序是指集合中仅有部分元素可比较大小(或先后)；全序是指集合中所有
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,
3、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,G.vertices1,G.vertices2,G.vertices3,G.vertices
4、4,G.vertices5,data,firstarc,adjvex,nextarc,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G.vertices0,G.vertices1,G.vertices2,G.vertices3,G.vertices4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,求indegree一维数
5、组初值的程序：,FindInDegree(ALGraph G,indegree0.G.vexnum-1,for(i=0;iG.vexnum;+i),p=G.verticesi.firstarc;,while(p),k=p-adjvex;,+indegreek;,p=p-nextarc;,/FindInDegree,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G.vertices0,G.vertices1,G.vertices2,G.vertices3,G.vertices4,G.vertices5,另外增设一
6、个存放各顶点的入度值的一维数组indegree:,indegree0.5,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,G
7、.vertices1,G.vertices2,G.vertices3,G.vertices4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G.vertices0,G.vertices1,G.vertices2,G.vertices3,G.vertices4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2
8、3 4 5,s,5,打印G.vertices5.data,4号和3号顶点的入度分别减1,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G.vertices0,G.vertices1,G.vertices2,G.vertices3,G.vertices4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,
9、4,G.vertices0,G.vertices1,G.vertices2,G.vertices3,G.vertices4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,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,G.vertices1,G.vertices2,G.vertices3,G.vertices4,G.vert
10、ices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G.vertices0,G.vertices1,G.vertices2,G.vertices3,G.vertices4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,
11、v3,2,v4,3,v6,5,v5,4,G.vertices0,G.vertices1,G.vertices2,G.vertices3,G.vertices4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,2,打印G.vertices2.data,4号、1号顶点的入度分别减1,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G.vertices0,G.vertices1,G.vertices2,G.vertices3,G.v
12、ertices4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G.vertices0,G.vertices1,G.vertices2,G.vertices3,G.vertices4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,1,打印G.vertices1.data,二、拓扑排序,4.
13、算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G.vertices0,G.vertices1,G.vertices2,G.vertices3,G.vertices4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G.vertices0,G.vertices1,G.vertices2,G.vertices3,G.v
14、ertices4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,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,G.vertices1,G.vertices2,G.vertices3,G.vertices4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s
15、,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G.vertices0,G.vertices1,G.vertices2,G.vertices3,G.vertices4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,4,打印G.vertices4.data,最后输出的拓扑序列为：v6v1v3v2v4v5,二、拓扑排序,4.程序：,Status TopologicalSort(ALGraph)FindIndegree(G,in
16、degree);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
17、(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,
18、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);,例如：对于
19、事件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
20、,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
21、,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,例如：求上例各顶点的最早开始时间和最迟开始时间：,0,6,4,5,7,7,16,14,18,18,14,16,10,7,8,6,6,0,三、关键路径,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,例如：求上例各顶点的最早开始时间和最迟开始时间：,0,6,4,5,7,7,
22、16,14,18,18,14,16,10,7,8,6,6,0,其中：v1,v2,v5,v7,v8,v9为关键活动。,作业：,1.试分析下面有向图的矩阵存储结构和邻接表存储结构：,a,b,c,d,1,2,3,4,2.试编写函数，求在无向图的邻接表类的对象G中各顶点vi的度。,3.试编写函数，在无向图的邻接表类的对象G中判断两个顶点vi和vj之间是否存在一条从vi到vj的路径（提示：利用深度或广度优先遍历函数）。,作业：,4.自己任意设计画出一个AOV网（即画出一个有向无环图，要求有8个以上的顶点），然后试着写出它的一个拓扑序列。,5.自己任意设计画出一个AOE网（即画出一个有向无环图，且边上有权值，要求有10个以上的顶点），然后试着写出各顶点的最早开始时间和最迟开始时间，并写出该图的若干条关键路径。,End,返回,
