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

Presentation on theme: "第七节 拓扑排序与关键路径."— Presentation transcript:

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

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

3 引入 　　在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本身，这显然出现了矛盾。

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

5 拓扑排序算法 算法实现： 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的点。 我们结合上图详细讲解： A B C D 开始时，只有A入度为0，A入栈。 栈：A

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

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

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

9 拓扑排序算法 【例4-12】、家谱树 【问题描述】 有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。 给出每个人的孩子的信息。
输出一个序列，使得每个人的后辈都比那个人后列出。 【输入格式】 第1行一个整数N（1<=N<=100），表示家族的人数。 接下来N行，第I行描述第I个人的儿子。 每行最后是0表示描述完毕。 【输出格式】 如果有多解输出任意一解。 【输入样例】 5 1 0 5 3 0 3 0 【输出样例】

10 拓扑排序算法 【参考程序】 //gentree #include<cstdio>
#include<iostream> using namespace std; int a[101][101],c[101],r[101],ans[101]; int i,j,tot,temp,num,n,m; int main() { freopen("gentree.in","r",stdin); freopen("gentree.out","w",stdout); cin >> n; for (i = 1; i <= n; i++) do cin >> j; if (j !=0 ) c[i]++; //c[i]用来存点i的出度 a[i][c[i]] = j; r[j]++; //r[i]用来存点i的入度。 } while (j != 0);

11 拓扑排序算法 for (i = 1; i <= n; i++) if (r[i] == 0)
ans[++tot] = i; //把图中所有入度为0的点入栈，栈用一维数组ans[]表示 do { temp = ans[tot]; cout << temp << " "; tot--;num++; //栈顶元素出栈并输出 for (i = 1; i <= c[temp]; i++) r[a[temp][i]]--; if (r[a[temp][i]] == 0) //如果入度减1后变成0，则将这个后继点入栈 ans[++tot] = a[temp][i]; } while (num != n); //如果输出的点的数目num等于n，说明算法结束 return 0;

12 拓扑排序算法 【例4-13】奖金 【问题描述】 　　由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。 【输入格式】 　　第一行两个整数n,m，表示员工总数和代表数；以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。 【输出格式】 　　若无法找到合理方案，则输出“Poor Xed”；否则输出一个数表示最少总奖金。 【输入样例】 　　2 1 　　1 2 【输出样例】 　　201

13 拓扑排序算法 【数据规模】 　　80％的数据满足n<=1000，m<=2000；100％的数据满足n<=10000，m<=20000。 【算法分析】 　　首先构图，若存在条件“a的钱比b多”则从b引一条有向指向a；然后拓扑排序，若无法完成排序则表示问题无解（存在圈）；若可以得到完整的拓扑序列，则按序列顺序进行递推： 设f[i]表示第i个人能拿的最少奖金数； 首先所有f[i]=100（题目中给定的最小值）； 　　 然后按照拓扑顺序考察每个点i，若存在有向边(j,i)，则表示f[i]必须比f[j]大，因此我们令f[i] = Max { f[i] , f[j]+1 }即可； 递推完成之后所有f[i]的值也就确定了，而答案就等于f[1]+…+f[n]。

14 拓扑排序算法 【参考程序】 #include<iostream> using namespace std;
int a[10001][301]={0},into[10001],ans[10001],m,n,money; void init() //读入数据，并构建图，统计入度 { int i,x,y; cin>>n>>m; for(i=1;i<=m;i++) { cin>>x>>y; a[y][0]++; //记录由y引出边的数目 a[y][a[y][0]]=x; //记录由a[y][0]引出边的顶点 into[x]++; //统计入度 } bool topsort() //拓扑排序 { int t,tot,k,i,j; tot=0;k=0; while(tot<n) //tot顶点个数 t=0; //用来判断有无环 for(i=1;i<=n;i++) if(into[i]==0)

15 拓扑排序算法 { tot++;t++;money+=100; ans[t]=i; into[i]=0xfffffff; }
if(t==0)return false; //存在环 money+=k*t;k++; for(i=1;i<=t;i++) //去掉相连的边 for(j=1;j<=a[ans[i]][0];j++)into[a[ans[i]][j]]--; return true; int main() init();money=0; if(topsort())cout<<money<<endl; else cout<<"Poor Xed"<<endl; return 0;

16 关键路径 　　利用AOV网络，对其进行拓扑排序能对工程中活动的先后顺序作出安排。但一个活动的完成总需要一定的时间，为了能估算出某个活动的开始时间，找出那些影响工程完成时间的最主要的活动，我们可以利用带权的有向网，图中的边表示活动，边上的权表示完成该活动所需要的时间，一条边的两个顶点分别表示活动的开始事件和结束事件，这种用边表示活动的网络，称为“AOE网”。 　　其中，有两个特殊的顶点（事件），分别称为源点和汇点，源点表示整个工程的开始，通常令第一个事件（事件1）作为源点，它只有出边没有入边；汇点表示整个工程的结束，通常令最后一个事件（事件n）作为汇点，它只有入边没有出边；其余事件的编号为2到n-1。 在实际应用中，AOE网应该是没有回路的，并且存在唯一的入度为0的源点和唯一的出度为0的汇点。 　　下图表示一个具有12个活动的AOE网。图中有8个顶点，分别表示事件0到7，其中，0表示开始事件，7表示结束事件，边上的权表示完成该活动所需要的时间。

17 关键路径 AOE网络要研究的问题是完成整个工程至少需要多少时间？哪些活动是影响工程进度的关键？
下面先讨论一个事件的最早发生时间和一个活动的最早开始时间。如下图，事件Vj必须在它的所有入边活动eik（1≤k≤n）都完成后才能发生。活动eik（1≤k≤n）的最早开始时间是与它对应的起点事件Vik的最早发生时间。所有以事件Vj为起点事件的出边活动ejk（1≤k≤m）的最早开始时间都等于事件Vj的最早发生时间。所以，我们可以从源点出发按照上述方法，求出所有事件的最早发生时间。

18 关键路径 设数组earliest[1..n]表示所有事件的最早发生时间，则我们可以按照拓扑顺序依次计算出earliest[k]：
　　　earliest[k]=max{earliest[j]+dut[j][k]} 　　　　　　　　(其中，事件j是事件k的直接前驱事件，dut[j][k]表示边<j，k>上的权) 　　对于上图，用上述方法求earliest[0..7]的过程如下： earliest[0]=0 earliest[1]=earliest[0]+dut[0][1]=0+6=6 earliest[2]=earliest[0]+dut[0][2]=0+7=7 earliest[4]=max{earliest[1]+dut[1][4]，earliest[2]+dut[2][4]} 　　　　=max{6+5,7+4} 　　　　=11 earliest[3]=max{earliest[1]+dut[1][3]，earliest[4]+dut[4][3]} 　　　　=max{6+3,11+3} 　　　　=14 earliest[5]=max{earliest[3]+dut[3][5]，earliest[4]+dut[4][5]} 　　　　=max{14+2,11+4} 　　　　=16 earliest[6]=earliest[4]+dut[4][6]=11+3=14 earliest[7]=max{earliest[3]+dut[3][7]，earliest[5]+dut[5][7], earliest[6]+dut[6][7]} 　　　　=max{14+5,16+2,14+4} 　　　　=19

19 关键路径 最后得到的earliest[7]就是汇点的最早发生时间，从而可知整个工程至少需要19天完成。
　　但是，在不影响整个工程按时完成的前提下，一些事件可以不在最早发生时间发生，而向后推迟一段时间，我们把事件最晚必须发生的时间称为该事件的最迟发生时间。同样，有些活动也可以推迟一段时间完成而不影响整个工程的完成，我们把活动最晚必须开始的时间称为该活动的最迟开始时间。一个事件在最迟发生时间内仍没发生，或一个活动在最迟开始时间内仍没开始，则必然会影响整个工程的按时完成。事件Vj的最迟发生时间应该为：它的所有直接后继事件Vjk（1≤k≤m）的最迟发生时间减去相应边<Vj，Vjk>上的权（活动ejk需要时间），取其中的最小值。且汇点的最迟发生时间就是它的最早发生时间，再按照逆拓扑顺序依次计算出所有事件的最迟发生时间，设用数组lastest[1..n]表示，即： 　　　lastest[n]=earliest[n] 　　　lastest[j]=min{lastest[k]-dut[j][k]} 　　　　　　　　　(其中，事件k是事件j的直接后继事件，dut[j,k]表示边<j，k>上的权) 　　对于上图，用上述方法求lastest [0..7]的过程如下： lastest[7]=earliest[7]=19 lastest[6]=lastest[7]-dut[6][7]=19-4=15 lastest[5]=lastest[7]-dut[5][7]=19-2=17 lastest[3]=min{lastest[5]-dut[3][5]，lastest[7]-dut[3][7]} =min{17-2,19-5} =14

20 关键路径 lastest[4]=min{lastest[3]-dut[4][3]，lastest[5]-dut[4][5], lastest[6]-dut[4][6]} =min{14-3,17-4,15-3} =11 lastest[2]=lastest[4]-dut[2][4]=11-4=7 lastest[1]=min{lastest[3]-dut[1][3]，lastest[4]-dut[1][4]} =min{14-3,11-5} =6 lastest[0]=min{lastest[1]-dut[0][1]，lastest[2]-dut[0][2]} =min{6-6,7-7} =0 计算好每个事件的最早和最迟发生时间后，我们可以很容易地算出每个活动的最早和最迟开始时间，假设分别用actearliest和actlastest数组表示，设活动i的两端事件分别为事件j和事件k,如下所示： 活动i 事件j ————————> 事件k 　　则：actearliest[i]=earliest[j] 　　　　actlastest[i]=lastest[k]-dut[j][k]

21 关键路径 对于上图，用上述方法求得所有活动的最早和最迟开始时间如下表：
<0,1> <0,2> <1,3> <1,4> <2,4> <3,5> <3,7> <4,3> <4,5> <4,6> <5,7> <6,7> 最早 6 7 14 11 16 最迟 15 13 12 17 余量 5 1 2 上表中的余量（称为开始时间余量）是该活动的最迟开始时间减去最早开始时间，余量不等于0的活动表示该活动不一定要在最早开始时间时就进行，可以拖延一定的余量时间再进行，也不会影响整个工程的完成。而余量等于0的活动必须在最早开始时间时进行，而且在规定的工期内完成，否则将影响整个工程的完成。 　　我们把开始时间余量为0的活动称为“关键活动”，由关键活动所形成的从源点到汇点的每一条路径称为“关键路径”。

22 关键路径 上图所示的AOE网的关键路径如下图所示。

23 上机练习 1、烦人的幻灯片 【问题描述】 　　李教授将于今天下午作一次非常重要的演讲。不信的事他不是一个非常爱整洁的人，他把自己演讲要用的幻灯片随便堆在了一起。因此，演讲之前他不得不去整理这些幻灯片。作为一个讲求效率的学者，他希望尽可能简单地完成它。教授这次演讲一共要用n张幻灯片（n<=26），这n张幻灯片按照演讲要使用的顺序已经用数字1~n编了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。 　　现在我们用大写字母A,B,C……再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若出现多种对应的情况或是某些数字编号和字母编号对应不起来，我们称对应是无法实现的。 【输入格式】 　　文件的第一行只有一个整数n，表示有n张幻灯片，接下来的n行每行包括4个整数xmin,xmax,ymin,ymax（整数之间用空格分开）为幻灯片的坐标，这n张幻灯片按其在文件中出现的顺序从前到后依次编号为A,B,C……，再接下来的n行依次为n个数字编号的坐标x,y，显然在幻灯片之外是不会有数字的。 【输出格式】 　　若是对应可以实现，输出文件应该包括n行，每一行为一个字母和一个数字，中间以一个空格隔开，并且每行以字母的升序排列，注意输出的字母要大写并且定格；反之，若是对应无法实现，在文件的第一行顶格输出None即可。首行末无多余的空格。 【输入输出样例】 slides.in slides.out 4 9 15 19 17 11 7 21 11 A 4 B 1 C 2 D 3

24 上机练习 2、病毒 【问题描述】 　　有一天，小y突然发现自己的计算机感染了一种病毒！还好，小y发现这种病毒很弱，只是会把文档中的所有字母替换成其它字母，但并不改变顺序，也不会增加和删除字母。 　　现在怎么恢复原来的文档呢！小y很聪明，他在其他没有感染病毒的机器上，生成了一个由若干单词构成的字典，字典中的单词是按照字母顺序排列的，他把这个文件拷贝到自己的机器里，故意让它感染上病毒，他想利用这个字典文件原来的有序性，找到病毒替换字母的规律，再用来恢复其它文档。 　　现在你的任务是：告诉你被病毒感染了的字典，要你恢复一个字母串。 【输入格式】virus.in 　　第一行为整数K（≤50000），表示字典中的单词个数。 　　以下K行，是被病毒感染了的字典，每行一个单词。 　　最后一行是需要你恢复的一串字母。 　　所有字母均为小写。 【输出格式】virus.out 　　　输出仅一行，为恢复后的一串字母。当然也有可能出现字典不完整、甚至字典是错的情况，这时请输出一个0。

25 上机练习 【输入样例】 　　6 　　cebdbac 　　cac 　　ecd 　　dca 　　aba 　　bac 　　cedab 【输出样例】 　　abcde