拓扑排序与关键路径(C++版).ppt

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：1.03M 资料格式：ppt 举报版权申诉

14e60876-c4dc-4be7-8817-b143aebf4f0c.ppt.pdf-第1页.png

第1页 / 共25页

14e60876-c4dc-4be7-8817-b143aebf4f0c.ppt.pdf-第2页.png

第2页 / 共25页

14e60876-c4dc-4be7-8817-b143aebf4f0c.ppt.pdf-第3页.png

第3页 / 共25页

14e60876-c4dc-4be7-8817-b143aebf4f0c.ppt.pdf-第4页.png

第4页 / 共25页

14e60876-c4dc-4be7-8817-b143aebf4f0c.ppt.pdf-第5页.png

第5页 / 共25页

14e60876-c4dc-4be7-8817-b143aebf4f0c.ppt.pdf-第6页.png

第6页 / 共25页

14e60876-c4dc-4be7-8817-b143aebf4f0c.ppt.pdf-第7页.png

第7页 / 共25页

14e60876-c4dc-4be7-8817-b143aebf4f0c.ppt.pdf-第8页.png

第8页 / 共25页

文本预览

第七节拓扑排序与关键路径

引入 AOV网在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为 “活动” ）组成的集合，这些子工程（活动）之间必定存在一些先后关系，即某些子工程（活动）必须在其它一些子工程（活动）完成之后才能开始，我们可以用有向图来形象地表示这些子工程（活动）之间的先后关系，子工程（活动）为顶点，子工程（活动）之间的先后关系为有向边，这种有向图称为“顶点活动网络” ，又称“AOV网” 。 1 2 3 4 5 6 7 9 8

引入　　在AOV网中，有向边代表子工程（活动）的先后关系，我们把一条有向边起点的活动成为终点活动的前驱活动，同理终点的活动称为起点活动的后继活动。而只有当一个活动全部的前驱全部都完成之后，这个活动才能进行。例如在上图中，只有当工程1完成之后，工程2、3、4、5、6才能开始进行。只有当2、3、4全部完成之后，7才能开始进行。　　一个AOV网必定是一个有向无环图，即不应该带有回路。否则，会出现先后关系的自相矛盾。 1 4 2 3 　　上图就是一个出现环产生自相矛盾的情况。4是1的前驱，想完成1，必须先完成4。3是4的前驱，而2是3的前驱，1又是2的前驱。最后造成想完成 1，必须先完成1本身，这显然出现了矛盾。

拓扑排序算法　拓扑排序算法，只适用于AOV网（有向无环图）。　　把AOV网中的所有活动排成一个序列，使得每个活动的所有前驱活动都排在该活动的前面，这个过程称为“拓扑排序”，所得到的活动序列称为“拓扑序列”。一个AOV网的拓扑序列是不唯一的，例如下面的这张图，它的拓扑序列可以是： ABCDE，也可以是ACBDE，或是ADBCE。在下图所示的AOV网中，工程B和工程 C显然可以同时进行，先后无所谓；但工程E却要等工程B、C、D都完成以后才能进行。 B E A C D 构造拓扑序列可以帮助我们合理安排一个工程的进度，由AOV网构造拓扑序列具有很高的实际应用价值。算法思想：　　构造拓扑序列的拓扑排序算法思想很简单：选择一个入度为0的顶点并输出然后从AOV网中删除此顶点及以此顶点为起点的所有关联边；重复上述两步，直到不存在入度为0的顶点为止。若输出的顶点数小于AOV网中的顶点数，则输出“有回路信息”，否则输出的顶点序列就是一种拓扑序列　　从第四步可以看出，拓扑排序可以用来判断一个有向图是否有环。只有有向无环图才存在拓扑序列。

拓扑排序算法算法实现： a) 数据结构：indgr[i]: 顶点i的入度; 　　 stack[ ]: 栈 b) 初始化:top=0 (栈顶指针置零) c) 将初始状态所有入度为0的顶点压栈 d) I=0 (计数器) e) while 栈非空(top>0) i. 栈顶的顶点v出栈；top-1; 输出v；i++； ii. for v的每一个后继顶点u 1. indgr[u]--; u的入度减1 2. if （u的入度变为0）顶点u入栈 f) 算法结束　　这个程序采用栈来找出入度为0的点，栈里的顶点，都是入度为0的点。我们结合上图详细讲解： B C A 开始时，只有A入度为0，A入栈。 D 栈：A

B C B C 拓扑排序算法 D D 栈顶元素A出栈并输出A，A的后继B、C入度减1，相当于删除A的所有关联边拓扑序列：A 栈：空 B、C的入度都变成0，依次将B、C入栈。拓扑序列：A 栈：BC（入栈顺序不唯一）

B 拓扑排序算法栈顶元素C出栈并输出C，C的后继D入度减1 拓扑序列：AC 栈：B 栈顶元素B出栈并输出B，B的后继D入度再减1。这时D入度为0，入栈。 D D 拓扑序列：ACB 栈：D

拓扑排序算法栈顶元素D出栈并输出D。栈空，结束 D 拓扑序列：ACBD（不唯一）栈：空简单&高效&实用的算法。上述实现方法复杂度O(V+E)。

分享到：

赞收藏

资料库

拓扑排序与关键路径(C++版).ppt

相关推荐

课程资源

热门标签

最新资料