信息学奥赛一本通第4章第7节拓扑排序与关键路径(C++版)剖析.ppt

第七节 拓扑排序与关键路径 引入 AOV网 在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为“活动” ）组成的集合，这些子工程（活动）之间必定存在一些先后关系，即某些子工程（活动）必须在其它一些子工程（活动）完成之后才能开始，我们可以用有向图来形象地表示这些子工程（活动）之间的先后关系，子工程（活动）为顶点，子工程（活动）之间的先后关系为有向边，这种有向图称为“顶点活动网络” ，又称“AOV网” 。 1 2 3 5 6 7 8 9 4 引入 　　在AOV网中，有向边代表子工程（活动）的先后关系，我们把一条有向边起点的活动成为终点活动的前驱活动，同理终点的活动称为起点活动的后继活动。而只有当一个活动全部的前驱全部都完成之后，这个活动才能进行。例如在上图中，只有当工程1完成之后，工程2、3、4、5、6才能开始进行。只有当2、3、4全部完成之后，7才能开始进行。 　　一个AOV网必定是一个有向无环图，即不应该带有回路。否则，会出现先后关系的自相矛盾。 1 2 3 4 　　上图就是一个出现环产生自相矛盾的情况。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都完成以后才能进行。 A B C E D 构造拓扑序列可以帮助我们合理安排一个工程的进度，由AOV网构造拓扑序列具有很高的实际应用价值。 算法思想： 　　构造拓扑序列的拓扑排序算法思想很简单： 选择一个入度为0的顶点并输出 然后从AOV网中删除此顶点及以此顶点为起点的所有关联边； 重复上述两步，直到不存在入度为0的顶点为止。 若输出的顶点数小于AOV网中的顶点数，则输出“有回路信息”，否则输出的顶点序列就是一种拓扑序列 　　从第四步可以看出，拓扑排序可以用来判断一个有向图是否有环。只有有向无环图才存在拓扑序列。 拓扑排序算法 算法实现： a) 数据结构：indgr[i]: 顶点i的入度; 　　 stack[ ]: 栈 b) 初始化:top=0 (栈顶指针置零) c) 将初始状态所有入度为0的顶点压栈 d) I=0 (计数器) e) while 栈非空(top0) i. 栈顶的顶点v出栈；top-1; 输出v；i++； ii. for v的每一个后继顶点u 1. indgr[u]--; u的入度减1 2. if （u的入度变为0） 顶点u入栈 f) 算法结束 　　这个程序采用栈来找出入度为0的点，栈里的顶点，都是入度为0的点。 我们结合上图详细讲解： A B C D 开始时，只有A入度为0，A入栈。 栈：A 拓扑排序算法 B C D 栈顶元素A出栈并输出A，A的后继B、C入度减1，相当于删除A的所有关联边 栈：空 拓扑序列：A B C D B、C的入度都变成0，依次将B、C入栈。 栈：BC（入栈顺序不唯一） 拓扑序列：A 拓扑排序算法 B D 栈顶元素C出栈并输出C，C的后继D入度减1 栈：B 拓扑序列：AC D 栈顶元素B出栈并输出B，B的后继D入度再减1。这时D入度为0，入栈。 栈：D 拓扑序列：ACB 拓扑排序算法 D 栈顶元素D出栈并输出D。栈空，结束 栈：空 拓扑序列：ACBD（不唯一） 简单高效实用的算法。上述实现方法复杂度O(V+E)。 拓扑排序算法 【例4-12】、家谱树 【问题描述】 有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。 给出每个人的孩子的信息。 输出一个序列，使得每个人的后辈都比那个人后列出。 【输入格式