拓扑排序(精)

2020/2/81第八章排序第七章图7.6拓扑排序拓扑排序的基本概念拓扑排序的基本要求拓扑排序的算法实现AOE网络及其应用2020/2/82第八章排序第七章图拓扑排序的基本概念图的应用产生满足时间制约有关的排序结果2020/2/83第八章排序第七章图与拓扑排序有关的基本概念研究对象：有向无环图逻辑含义：定点表示某种活动，有向边表示活动之间次序上的制约关系工作目标：构造图中顶点满足次序制约关系的线性序列，这个序列称为拓扑序列，2020/2/84第八章排序第七章图与拓扑排序有关的应用实例1：工程设计（设计、勘测、外部施工、内部施工（内部的次序）……）实例2：课程设置，包含先休课程之间的制约关系实例3：房屋装修，墙壁，门框，地板，门2020/2/85第八章排序第七章图拓扑排序要求与特点：对于有向无环图结点的一种排序若结点V与结点U之间存在V到U的边，则在拓扑序列中结点V一定排列在结点U之前。最终的结果是一个满足时间制约关系结点序列存在环路的有向图不存在拓扑序列。因为环路导致序列不可能满足上述原则。一个有向无环图的拓扑序列不唯一。2020/2/86第八章排序AOV图与拓扑排序有关的概念AOV图：有向无环图的一种名称，由于这种图往往只由活动于它们次序间的制约关系构成，所以图又称为“活动网络”，英文表示为：ActivityOnVertexAOV（活动顶点）。通常，拓扑排序就是针对AOV图来考虑的。AOV图的拓扑序列，就是满足图中结点之间次序制约关系的结点序列。2020/2/87第八章排序拓扑排序的控制思想有向无环图，至少存在一个以上入度为0的结点，该类结点就是拓扑序列的起始结点，在工程上就表示工程中第一步可做的工作。处理一个结点的操作就是删除该结点的所有出边。这一操作的结果可以导致，当某一结点的直接前驱结点都处理完成，则该结点的入度就为0了。在课程设置上表示，当某课程的所有先修课都学过了，这门课程就可以选修（激活）了。基于上述思想我们讨论拓扑排序的程序设计。2020/2/88第八章排序第七章图拓扑排序的实现我们将考虑几种实现拓扑排序过程，对于含有回路的有向图，算法将说明，图中含有回路，不存在拓扑排序。2020/2/89第八章排序拓扑排序算法说明-11.存储结构：邻接矩阵与辅助结构，结点数为N2.计算所有未处理结点的入度（不存在未处理结点结束）3.选取入度为0的结点V4.满足要求的V存在吗？存在goto5，否则goto75.输出V；删除V所有出边；标记V的处理结束6.修正处理结点计数器total++;goto2;7.提示“ring”,（若totalN则图中含有环）结束此时输出的结点序列就是图的拓扑序列2020/2/810第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd01122020/2/811第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0112输出：a2020/2/812第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0112输出：a删除a的所有出边2020/2/813第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0112输出：a建立a的处理结束标记2020/2/814第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0112输出：a计算结点入边（列）2020/2/815第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0112输出：a，b删除b的出边2020/2/816第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0112输出：a，b调整邻接矩阵2020/2/817第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0002输出：a，b作结点b结束标志2020/2/818第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0111输出：a，b计算结点的入度（列）2020/2/819第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0111输出：a，b，c..2020/2/820第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0111输出：a，b，c删除结点C的出边2020/2/821第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0111输出：a，b，c调整邻接句矩阵2020/2/822第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0111输出：a，b，c结点c处理结束2020/2/823第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0110输出：a，b，c调整结点入度（列）2020/2/824第八章排序拓扑排序过程算法说明：abcdABCDA0110B0001C0001D0000abcd0110输出：a，b，c，d….2020/2/825第八章排序拓扑排序算法--2存储结构：邻接表，处理结点记录数组邻接表：表头带有数据域，记录节点的入度，邻接表选择出边邻接表（课本算法过程）处理过程：1.计算各个结点的入度2.选择入度为零的结点进栈st3.从堆栈中取出节点i=st[top]4.根据邻接表adj，将节点i的所有直接后继结点的入度-1，若入度为0则结点进栈5.重复3-4，直到栈空处理过程使用堆栈和队列都可以得到拓扑序列，只是序列不同。队列能够反映并行展开的结点的状态。2020/2/826第八章排序拓扑排序算法--3存储结构：邻接表，处理结点记录数组邻接表：表头带有数据域，记录节点的入度，邻接表选择出边邻接表处理过程：1.计算各个结点的入度2.选择入度为零且尚未处理过的结点k3.根据邻接表，将所有直接后继结点的入度-14.标记结点处理结束，即入度标记为-15.重复2-4，直到所有的结点入度标记为-12020/2/827第八章排序拓扑排序算法1.构建邻接表存储结构结点结构：structnode{vertexdata；structnode*next；}头指针数组结构：typedefstruct{vertexdata;//结点标志keyintcount；//入度记录structnode*firstarc；}headv；headvh[total];structnode*wp;2020/2/828第八章排序拓扑排序算法--31.构建邻接表存储结构的逻辑表达132530425-163datafirstarc216^count2020/2/829第八章排序拓扑排序算法--22.所有邻接点入度-1处理过程if(h[k].count==0){printf（“%d”，h[k].data）;wp=h[k].firstarc;//指向第一个邻接点while(wp!=NULL)//单链表未结束{h[wp-data].count--;//相应结点入度-1wp=wp-next;}h[k].count=-1;//标志结点处理结束}当所有结点的count为-1时，处理结束2020/2/830第八章排序拓扑排序实例0142530,4,1,2,5,3;0,4,1,5,2,3;0,4,5,1,2,34,0,1,2,5,3;4,0,1,5,2,3;4,0,5,1,2,34,5,0,1,2,3;……2020/2/831第八章排序拓扑排序的要求了解拓扑排序的算法思想对指定的数据序列能写出其所有的拓扑序列2020/2/832第八章排序AOE网络与关键路径所有的工程或系统都可以分为若干个称作活动（activity）的子工程，而这些子工程之间，通常存在着一定的制约关系，如其中的某些子工程必须在另外一些子工程完成之后开始。对于整个工程或系统，我们关心的是两个方面的问题：工程能否顺利完成？（AOV网络）工程完成所必需的最短时间？（AOE网络）2020/2/833第八章排序AOV网AOV（ActivityOnVertexNetwork）：用顶点表示活动，用边表示活动间的优先(制约)关系的有向图，称为顶点表示活动的网络，简称为AOV网。2020/2/834第八章排序AOV网利用AOV网络，我们试图解决各个活动之间的关系问题，典型的实例：教学计划制定中课程及课程间的先修关系可用AOV网表示任何无环路的AOV网，其顶点都可以排成一个拓扑序列，并且其拓扑序列不一定是唯一的。2020/2/835第八章排序123456789102020/2/836第八章排序AOE网AOE网（ActivityOnEdgeNetwork）在带权的有向图中，用结点表示事件，用边表示活动，边上权表示活动的开销（如持续时间），则称此有向图为边表示活动的网络,简称AOE网。下图是有11项活动，9个事件的AOE网，每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。2020/2/837第八章排序AOE网络因为活动可以并行，从源点到汇点存在多条路径带权路径长度最长的路径成为“关键路径”关键路径中活动称为“关键活动”2020/2/838第八章排序AOE网AOE网的性质：①只有在某个顶点所代表的事件发生后，从该顶点出发的各有向边代表的活动才能开始;②只有在进入某一顶点的各有向边代表的活动已经结束，该顶点所代表的事件才能发生；③表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度为0的开始顶点（源点）和唯一的出度为0的结束点（汇点）。2020/2/839第八章排序AOE网AOE网研究的主要问题：如果用AOE网表示一项工程，那么仅仅考虑各个子工程之间的优先关系还不够，更多地是关心整个工程完成的最短时间是多少，哪些活动的延迟将影响整个工程进度,而加速这些活动能否提高整个工程的效率,因此AOE网有待研究的问题是:①完成整个工程至少需要多少时间？②哪些活动是影响工程进度的关键活动？由于工程中某些活动是可以并行的，所以并不是缩短任一活动的时间都能够达到缩短整个工程工期的目的。2020/2/840第八章排序关键路径与关键活动性质分析考察关键路径描述的特征点（参数）：①事件Vj的可能发生的最早时间VE(j)：是从源点V1到顶点Vj的最长路径长度。②活动ai可能开始的最早时刻E(k)：设活动ai在边Vj,Vk上,则E(i)也就是从源点V1到顶点Vj的最长路径长度。这是因为事件Vj发生表明以Vj为起点的所有活动ai可以立即开始。③因此有：E(i)=VE(j)…………..(1)即：活动最少开始时间就是相应起始结点事件开始的最早时间。2020/2/841第八章排序关键路径与关键活动④事件Vk的最迟发生时间VL(k)：是指在保证汇点Vn在VE(n)时刻完成的前提下，事件Vk允许的最迟开始时间。就是说：在不推迟工期的情况下，事件Vk最迟发生时间VL(k)应该等于汇点的最早发生时间VE(n)减去从Vk到Vn的最大路径长度。2020/2/842第八章排序关键路径与关键活动⑤活动ai允许的最迟开始时间L(i)：是指在不会引起工期延误的前提下，活动ai允许的最迟开始时间。因为事件Vk发生表明以Vk为终点的入边所表示的所有活动均已完成，所以事件Vk的最迟发生时间VL(k)也是所有以Vk为终点的入边：Vj,Vk所表示的活动ai可能的最迟完成时间。⑥所以，若要保证不推迟工期，活动ai的最迟开始时间L(i)应该是ai的最迟完成时间VL(k)减去ai的持续时间，即：L(i)=VL(k)-ACT[j][k]…………..(2)其中,ACT[j][k]是活动ai的持续时间