拓扑排序关键路径

1、AOV 网在日常生活中，一项大的工程可以看作是由若干 个子工程（这些子工程称为“活动”）组成的集合， 这些子工程（活动）之间必定存在一些先后关系，即 某些子工程（活动）必须在其他一些子工程（活动） 完成之后才能开始，我们可以用有向图来形象地表示 这些子工程（活动）之间的先后关系，子工程（活动） 为顶点，子工程（活动）之间的先后关系为有向边， 这种有向图称为“顶点活动网络”，又称AOV网。一个AOV网应该是一个有向无环图，即不应该带 有回路，否则必定会有一些活动互相牵制，造成环中 的活动都无法进行。拓扑排序：把不带回路AOV网中所有活动排成一个线性序列， 使得每个活动的所有前驱活动都排在该活动的

2、前 面，这个过程成为“拓扑排序”,所得到的活动 序列称为“拓扑序列” o需要注意的是AOV网的 _拓扑序列是不唯一的。如图有以下几种拓扑序列:02143567、 01243657、 02143657、 01243567拓扑排序算法思想选择入度为0且不在已排序的序列中的顶点，然后从AOV网中删除此顶点及以此顶 点为起点的所有关联的边；重复上述两 步，直到不存在入度为0的顶点为止。若 输出的顶点数小于AOV网中的顶点数,则输出“有回路信息",否则输出的顶点 序列就是一种拓扑序列。拓扑序列模拟：01243567算法框架：（采用邻接矩阵描述）Program aov(i叩utz output)

3、;const maxvtxnum=100;=var g:arrayO.maxvtxnum, 1. maxvtxnum of integer;s；array 1.maxvtxnum of boolean; 标记数组 ( Iist:arrayl.maxvtxnum of integer; 记录拓扑序列 rj.knnnteger;beginassign(input, 'aov. irf ); reset(input);assign(output # 5aov out5);rewr 汁 e(ou 十 pu 十)；.readln(n); for i： = l to n do)for j： = l

4、 to n do read(gij); for i： = l to n do si： =false；for k： = l to n dobeginfor j： = l to n dobegin90J：=0；统计顶点的入度for i： = l to n do gO,jngO,j*9i,j： end;j： = l； 查找入度为0,且未在序列中出现过 while (g0J>0) or sj) and (j<n) do j：=j+l； if j>n then exit; 存在环 listk：=j; sj：=true;for i： = l to n do gjJ：=O; end;if

5、k<n then write(4rror5)else for i： = l to n do write(listi：2); close(input); close(output);End.应用实例士兵排队5【问题描述】有n个士兵（l£n<26）,编号依次为A、B、C队列训练时，指挥官要把一些士兵从髙到矮依次排成 一行。但现在指挥官不能直接获得每个人的身高信息，只 能获得“pl比p2高"这样的比较结果（pl,P2G CA ./z5）,记为pl>P2o根据这些关系，求出排 队方案。假设比豪结果为：A>B,B>D,F>D,B>F ,则排队

6、方案为ABFD输入数据第一行：n第二行：ri个大写字母（表示士兵编号）；第三行：k （表示高矮关系个数）； 接工来k行：pl p2（表示高矮关系）AOE网耳一个活动的完成总需要一定的时间，为了能估算出囁 个活动的开始时间，找出那些影响工程完成时间的最 主要的活动，我们可以利用带权的有向图。图中的边 表示活动，边上的权表示完成该活动所需要的时间， 一条边的两个顶点分别表示活动的开始事件和结束事 件，这种用边表示活动的网络，称为“A0E网” o其 中两个特殊的顶点（事件），分别称为源点和汇点。源点表示整个工程的开始，通常令第一个事件作为源 点，它只有出边没有入边；汇点表示整个工程的结束, 通常令最

7、后一个事件（事件口）作为汇点，它只有入 边没有出边；其余事件的编号为2到旷1。在实际应用 中，A0E网应该没有回路的，并且存在唯一的入度为0AOE网研究的问题：1.完成整项工程至少需要多少时间？2 哪些活动是影响工程进度的关键？关键路径由于在AOE网中有些活动可以并行地进行，所以完成 工程的最短时间是从源点到汇点的最长路径的长度。 路径长度最长的路径叫做关键路径。引入两个定义事件的最早发生时间：时间0最早发生时间是0,事件7的最早发生时间是整个工程最快完 成时间，事件4的发生时间是以4为终点的所 有弧上活动全部完成的最快时间。事件的最迟发生时间：由于0是整个工程的起 点，因此事件0的最迟发生时

8、间是0,事件4的 最迟发生时间是保证不影响进度的前提下最迟 可以发生的时间。显然，事件7的最早发生时间和最迟发生时间 相等。最早发生时间的计算 ¥ 设数组earliestl.n表示所有事件的最 早发生时间，则我们可以按照拓扑排序 依次计算出earl iestk; Earliestl=O Earliestk二maxearliestj+dutj,l （其中，事件j是事件k的直接前驱事件，dutj,k表示边j,k上的权。）706最迟发生时间的计算千设用数组lastestl.n表示最迟发生时I】 按照逆拓扑排序依次计算出所有事件的 最迟发生时向： Las tes 十n二 earliest n Lastestj=minlastestk-dutj/k（其中，事件k是事件j的直接后继事件,dutj,k表示边j,k上的权。）关键路径的计算01243567earliest067Max (1111)=11Max14) =14Max (16.15) =1614Max (18. j18- 19)/ 二 19#lastest067Min (11.13. 12) =11Min <14.15)=14171519、从表中可以看出，事件0