《有向无环图及其应用讲解课件》由会员分享，可在线阅读，更多相关《有向无环图及其应用讲解课件（35页珍藏版）》请在金锄头文库上搜索。
1、1,有向无环图及其应用,2,一、定义,一个无环的有向图称为有向无环图，简写为DAG（directed acycline graph）。 与有向二叉树相比，有向无环图是更一般的特殊有向图。,实例：,有向树,有向无环图,有向图,有向无环图的一个简单应用： 用有向无环图描述算术表达式。,3,二、拓扑排序,1.引例：现有计算机课程12门，如下表所示：,C1,C9,C4,C2,C12,C10,C11,C3,C5,C6,C7,C8,4,二、拓扑排序,C1,C9,C4,C2,C12,C10,C11,C3,C5,C6,C7,C8,2.拓扑排序：,偏序是指集合中仅有部分元素可比较大小(或先后)； 全序是指集合中
2、所有元素均可比较大小（或先后）。,5,二、拓扑排序,C1,C9,C4,C2,C12,C10,C11,C3,C5,C6,C7,C8,2.拓扑排序：,拓扑排序是指将一个偏序关系转化为全序关系的过程的特殊操作。,6,二、拓扑排序,C1,C9,C4,C2,C12,C10,C11,C3,C5,C6,C7,C8,3.方法：,在有向图中选择一个没有前驱（即入度为0）的顶点并输出之。,在有向图中删除刚刚输出的顶点及所有以该顶点为尾的弧。,图中若不再有入度为0的顶点，则结束；否则转。,7,二、拓扑排序,C1,C9,C4,C2,C12,C10,C11,C3,C5,C6,C7,C8,3.方法：,C1,拓扑序列：,C
3、2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8,8,二、拓扑排序,3.方法：,注意1 :从某种意义下来说，拓扑排序的结果是不唯一的。,注意2 :这种以顶点表示活动的有向无环图称为活动在顶点的网,简称AOV(Activity On Vertex Network)网。,C1,拓扑序列：,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8,9,二、拓扑排序,3.方法：,注意1 :从某种意义下来说，拓扑排序的结果是不唯一的。,注意2 :这种以顶点表示活动的有向无环图称为活动在顶点的网,简称AOV(Activity On Vertex Network)网。,注意
4、3 :当有向图中包含有向环路时，拓扑排序算法结束时图中还有若干顶点没有被输出（即有向环路中的所有顶点没有参加排序）。,10,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G.adjlist0,G.adjlist1,G.adjlist2,G.adjlist3,G.adjlist4,G. adjlist5,vertex,firstedge,adjvex,nextadj,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,11,二、拓扑排序,4.算法说明：为了使
5、说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,G. adjlist1,G. adjlist2,G. adjlist3,G. adjlist4,G. adjlist5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,求indegree一维数组初值的程序：,FindInDegree(ALGraph G,indegree0.G.vexnum-1),for(i=0;iG.vexnum;+i),p=G. adjlisti.firstedge;,while (p),k=p-
6、adjvex;,+indegreek;,p=p-nextadj;,/FindInDegree,for(i=0;iG.vexnum;+i) indegree0.G.vexnum-1=0;,12,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,Gadjlist 1,G. adjlist2,G. adjlist3,Gadjlist 4,G. adjlist5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,拓扑排序算法思想： 设一个栈S
7、，所有入度为0的顶点的序号进栈。如0，5 进栈。count=0(打印顶点个数计数器)。,当栈S不空时，出栈一个元素并打印相应顶点的值；count加1。,该顶点的所有邻接点的入度减1，减1后所有入度为0的顶点的序号进栈。,重复第二步，直至栈空时转。,若count=G.vexnum,则拓扑排序成功；否则图中必有环路，拓扑排序失败。,13,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,G. adjlist1,G. adjlist2,G. adjlist3,G. adjlist4,Gadjlis
8、t 5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,14,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,G. adjlist1,G. adjlist2,G. adjlist3,G. adjlist4,G. adjlist5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,5,打印G. adjlist5.data,4号和3号顶点的入度分别减1,15,二、拓扑排
9、序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,G. adjlist1,G. adjlist2,G. adjlist3,G. adjlist4,G. adjlist5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,16,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,G. adjlist1,G. adjlist2,G. adjli
10、st3,G. adjlist4,G. adjlist5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,0,打印G. adjlist0.data,3号、2号、1号顶点的入度分别减1,17,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,G. adjlist1,G. adjlist2,G. adjlist3,G. adjlist4,G. adjlist5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegre
11、e0.5,0 1 2 3 4 5,s,18,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,G. adjlist1,G. adjlist2,G. adjlist3,G. adjlist4,G. adjlist5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,19,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,G. ad
12、jlist1,G. adjlist2,G. adjlist3,G. adjlist4,G.vertices5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,2,打印G. adjlist2.data,4号、1号顶点的入度分别减1,20,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,G. adjlist1,G. adjlist2,G. adjlist3,G. adjlist4,G. adjlist5,另外增设一个存放各顶点的入
13、度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,21,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,G. adjlist1,G. adjlist2,G. adjlist3,G. adjlist4,G. adjlist5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,1,打印G.vertices1.data,22,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1
14、,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,G. adjlist1,G. adjlist2,G. adjlist3,G. adjlist4,G. adjlist5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,23,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,G. adjlist1,G. adjlist2,G. adjlist3,G. adjlist4,G. adjlist5,另外增设一个存放各顶点的入度值的一维数组indegree:,indegree0.5,0 1 2 3 4 5,s,3,打印G. adjlist3.data,4号顶点的入度减1,24,二、拓扑排序,4.算法说明：为了使说明过程简单起见，我们以下图为例：,v1,0,v2,1,v3,2,v4,3,v6,5,v5,4,G. adjlist0,G. adjlist1,G. adjlist2,G. adjl
