第4章第7節(jié)拓撲排序與關鍵路徑(C++版)

1、第七節(jié)第七節(jié) 拓撲排序與關鍵路徑拓撲排序與關鍵路徑引入AOV網 在日常生活中，一項大的工程可以看作是由若干個子工程（這些子工程稱為“活動” ）組成的集合，這些子工程（活動）之間必定存在一些先后關系，即某些子工程（活動）必須在其它一些子工程（活動）完成之后才能開始，我們可以用有向圖來形象地表示這些子工程（活動）之間的先后關系，子工程（活動）為頂點，子工程（活動）之間的先后關系為有向邊，這種有向圖稱為“頂點活動網絡” ，又稱“AOV網” 。123567894引入在AOV網中，有向邊代表子工程（活動）的先后關系，我們把一條有向邊起點的活動成為終點活動的前驅活動，同理終點的活動稱為起點活動的后繼活動。

2、而只有當一個活動全部的前驅全部都完成之后，這個活動才能進行。例如在上圖中，只有當工程1完成之后，工程2、3、4、5、6才能開始進行。只有當2、3、4全部完成之后，7才能開始進行。一個AOV網必定是一個有向無環(huán)圖，即不應該帶有回路。否則，會出現(xiàn)先后關系的自相矛盾。1234上圖就是一個出現(xiàn)環(huán)產生自相矛盾的情況。4是1的前驅，想完成1，必須先完成4。3是4的前驅，而2是3的前驅，1又是2的前驅。最后造成想完成1，必須先完成1本身，這顯然出現(xiàn)了矛盾。拓撲排序算法 拓撲排序算法，只適用于AOV網（有向無環(huán)圖）。把AOV網中的所有活動排成一個序列， 使得每個活動的所有前驅活動都排在該活動的前面，這個過程稱

3、為“拓撲排序”，所得到的活動序列稱為“拓撲序列”。一個AOV網的拓撲序列是不唯一的，例如下面的這張圖，它的拓撲序列可以是：ABCDE，也可以是ACBDE，或是ADBCE。在下圖所示的AOV網中，工程B和工程C顯然可以同時進行，先后無所謂；但工程E卻要等工程B、C、D都完成以后才能進行。ABCED構造拓撲序列可以幫助我們合理安排一個工程的進度，由AOV網構造拓撲序列具有很高的實際應用價值。算法思想：構造拓撲序列的拓撲排序算法思想很簡單：選擇一個入度為0的頂點并輸出然后從AOV網中刪除此頂點及以此頂點為起點的所有關聯(lián)邊；重復上述兩步，直到不存在入度為0的頂點為止。若輸出的頂點數(shù)小于AOV網中的頂點

4、數(shù)，則輸出“有回路信息”，否則輸出的頂點序列就是一種拓撲序列從第四步可以看出，拓撲排序可以用來判斷一個有向圖是否有環(huán)。只有有向無環(huán)圖才存在拓撲序列。拓撲排序算法 算法實現(xiàn)： a) 數(shù)據結構：indgri: 頂點i的入度; stack : 棧 b) 初始化:top=0 (棧頂指針置零) c) 將初始狀態(tài)所有入度為0的頂點壓棧 d) I=0 (計數(shù)器) e) while 棧非空(top0) i. 棧頂?shù)捻旤cv出棧；top-1; 輸出v；i+； ii. for v的每一個后繼頂點u 1. indgru-; u的入度減1 2. if （u的入度變?yōu)?） 頂點u入棧 f) 算法結束這個程序采用棧來找出入

5、度為0的點，棧里的頂點，都是入度為0的點。我們結合上圖詳細講解：ABCD開始時，只有A入度為0，A入棧。棧：A拓撲排序算法 BCD棧頂元素A出棧并輸出A，A的后繼B、C入度減1，相當于刪除A的所有關聯(lián)邊棧：空拓撲序列：ABCDB、C的入度都變成0，依次將B、C入棧。棧：BC（入棧順序不唯一）拓撲序列：A拓撲排序算法 BD棧頂元素C出棧并輸出C，C的后繼D入度減1棧：B拓撲序列：ACD棧頂元素B出棧并輸出B，B的后繼D入度再減1。這時D入度為0，入棧。棧：D拓撲序列：ACB拓撲排序算法 D棧頂元素D出棧并輸出D。棧空，結束棧：空拓撲序列：ACBD（不唯一）簡單&高效&實用的算法。

6、上述實現(xiàn)方法復雜度O(V+E)。拓撲排序算法 【例4-12】、家譜樹【問題描述】 有個人的家族很大，輩分關系很混亂，請你幫整理一下這種關系。 給出每個人的孩子的信息。 輸出一個序列，使得每個人的后輩都比那個人后列出?！据斎敫袷健?第1行一個整數(shù)N（1=N=100），表示家族的人數(shù)。 接下來N行，第I行描述第I個人的兒子。 每行最后是0表示描述完畢?！据敵龈袷健?輸出一個序列，使得每個人的后輩都比那個人后列出。 如果有多解輸出任意一解。【輸入樣例】 5 0 4 5 1 0 1 0 5 3 0 3 0【輸出樣例】 2 4 5 3 1拓撲排序算法 【參考程序】/gentree#include#inc

7、ludeusing namespace std;int a101101,c101,r101,ans101;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 j; if (j !=0 ) ci+; /ci用來存點i的出度 aici = j; rj+; /ai,-1用來存點i的入度。 while (j != 0); 拓撲排序算法 for (i = 1; i = n; i+) if (ri = 0) ans+tot =

8、 i; /把圖中所有入度為0的點入棧，棧用一維數(shù)組ans表示 do temp = anstot; cout temp ; tot-;num+; /棧頂元素出棧并輸出 for (i = 1; i = ctemp; i+) ratempi-; if (ratempi = 0) /如果入度減1后變成0，則將這個后繼點入棧 ans+tot = atempi; while (num != n); /如果輸出的點的數(shù)目num等于n，說明算法結束 return 0;拓撲排序算法 【例4-13】獎金【問題描述】由于無敵的凡凡在2005年世界英俊帥氣男總決選中勝出，Yali Company總經理Mr.Z心情好，

9、決定給每位員工發(fā)獎金。公司決定以每個人本年在公司的貢獻為標準來計算他們得到獎金的多少。于是Mr.Z下令召開m方會談。每位參加會談的代表提出了自己的意見：“我認為員工a的獎金應該比b高！”Mr.Z決定要找出一種獎金方案，滿足各位代表的意見，且同時使得總獎金數(shù)最少。每位員工獎金最少為100元。 【輸入格式】第一行兩個整數(shù)n,m，表示員工總數(shù)和代表數(shù)；以下m行，每行2個整數(shù)a,b，表示某個代表認為第a號員工獎金應該比第b號員工高。 【輸出格式】若無法找到合理方案，則輸出“Poor Xed”；否則輸出一個數(shù)表示最少總獎金?！据斎霕永? 11 2【輸出樣例】201拓撲排序算法 【數(shù)據規(guī)?！?0的數(shù)據滿

10、足n=1000，m=2000；100的數(shù)據滿足n=10000，m=20000?！舅惴ǚ治觥渴紫葮媹D，若存在條件“a的錢比b多”則從b引一條有向指向a；然后拓撲排序，若無法完成排序則表示問題無解（存在圈）；若可以得到完整的拓撲序列，則按序列順序進行遞推： 設fi表示第i個人能拿的最少獎金數(shù)； 首先所有fi=100（題目中給定的最小值）； 然后按照拓撲順序考察每個點i，若存在有向邊(j,i)，則表示fi必須比fj大，因此我們令fi = Max fi , fj+1 即可； 遞推完成之后所有fi的值也就確定了，而答案就等于f1+fn。拓撲排序算法 【參考程序】#includeusing namespa

11、ce std;int a10001301=0,into10001,ans10001,m,n,money;void init() /讀入數(shù)據，并構建圖，統(tǒng)計入度 int i,x,y; cinnm; for(i=1;ixy; ay0+; /記錄由y引出邊的數(shù)目 ayay0=x; /記錄由ay0引出邊的頂點 intox+; /統(tǒng)計入度 bool topsort() /拓撲排序 int t,tot,k,i,j; tot=0;k=0; while(totn) /tot頂點個數(shù) t=0; /用來判斷有無環(huán) for(i=1;i=n;i+) if(intoi=0) 拓撲排序算法 tot+;t+;money+=

12、100; anst=i; intoi=0 xfffffff; if(t=0)return false; /存在環(huán) money+=k*t;k+; for(i=1;i=t;i+) /去掉相連的邊 for(j=1;j=aansi0;j+)intoaansij-; return true;int main() init();money=0; if(topsort()coutmoneyendl; else coutPoor Xedendl; return 0;關鍵路徑 利用AOV網絡，對其進行拓撲排序能對工程中活動的先后順序作出安排。但一個活動的完成總需要一定的時間，為了能估算出某個活動的開始時間，找出

13、那些影響工程完成時間的最主要的活動，我們可以利用帶權的有向網，圖中的邊表示活動，邊上的權表示完成該活動所需要的時間，一條邊的兩個頂點分別表示活動的開始事件和結束事件，這種用邊表示活動的網絡，稱為“AOE網”。其中，有兩個特殊的頂點（事件），分別稱為源點和匯點，源點表示整個工程的開始，通常令第一個事件（事件1）作為源點，它只有出邊沒有入邊；匯點表示整個工程的結束，通常令最后一個事件（事件n）作為匯點，它只有入邊沒有出邊；其余事件的編號為2到n-1。在實際應用中，AOE網應該是沒有回路的，并且存在唯一的入度為0的源點和唯一的出度為0的匯點。下圖表示一個具有12個活動的AOE網。圖中有8個頂點，分別

14、表示事件0到7，其中，0表示開始事件，7表示結束事件，邊上的權表示完成該活動所需要的時間。關鍵路徑 AOE網絡要研究的問題是完成整個工程至少需要多少時間？哪些活動是影響工程進度的關鍵？下面先討論一個事件的最早發(fā)生時間和一個活動的最早開始時間。如下圖，事件Vj必須在它的所有入邊活動eik（1kn）都完成后才能發(fā)生。活動eik（1kn）的最早開始時間是與它對應的起點事件Vik的最早發(fā)生時間。所有以事件Vj為起點事件的出邊活動ejk（1km）的最早開始時間都等于事件Vj的最早發(fā)生時間。所以，我們可以從源點出發(fā)按照上述方法，求出所有事件的最早發(fā)生時間。關鍵路徑 設數(shù)組earliest1.n表示所有事件

15、的最早發(fā)生時間，則我們可以按照拓撲順序依次計算出earliestk：earliest1=0earliestk=maxearliestj+dutjk (其中，事件j是事件k的直接前驅事件，dutjk表示邊上的權)對于上圖，用上述方法求earliest0.7的過程如下：earliest0=0earliest1=earliest0+dut01=0+6=6earliest2=earliest0+dut02=0+7=7earliest4=maxearliest1+dut14，earliest2+dut24=max6+5,7+4=11earliest3=maxearliest1+dut13，earlies

16、t4+dut43=max6+3,11+3=14earliest5=maxearliest3+dut35，earliest4+dut45=max14+2,11+4=16earliest6=earliest4+dut46=11+3=14earliest7=maxearliest3+dut37，earliest5+dut57, earliest6+dut67=max14+5,16+2,14+4=19關鍵路徑 最后得到的earliest7就是匯點的最早發(fā)生時間，從而可知整個工程至少需要19天完成。但是，在不影響整個工程按時完成的前提下，一些事件可以不在最早發(fā)生時間發(fā)生，而向后推遲一段時間，我們把事件最

17、晚必須發(fā)生的時間稱為該事件的最遲發(fā)生時間。同樣，有些活動也可以推遲一段時間完成而不影響整個工程的完成，我們把活動最晚必須開始的時間稱為該活動的最遲開始時間。一個事件在最遲發(fā)生時間內仍沒發(fā)生，或一個活動在最遲開始時間內仍沒開始，則必然會影響整個工程的按時完成。事件Vj的最遲發(fā)生時間應該為：它的所有直接后繼事件Vjk（1km）的最遲發(fā)生時間減去相應邊上的權（活動ejk需要時間），取其中的最小值。且匯點的最遲發(fā)生時間就是它的最早發(fā)生時間，再按照逆拓撲順序依次計算出所有事件的最遲發(fā)生時間，設用數(shù)組lastest1.n表示，即：lastestn=earliestnlastestj=minlastestk

18、-dutjk (其中，事件k是事件j的直接后繼事件，dutj,k表示邊上的權)對于上圖，用上述方法求lastest 0.7的過程如下：lastest7=earliest7=19lastest6=lastest7-dut67=19-4=15lastest5=lastest7-dut57=19-2=17lastest3=minlastest5-dut35，lastest7-dut37 =min17-2,19-5 =14關鍵路徑 lastest4=minlastest3-dut43，lastest5-dut45, lastest6-dut46 =min14-3,17-4,15-3 =11lastes

19、t2=lastest4-dut24=11-4=7lastest1=minlastest3-dut13，lastest4-dut14 =min14-3,11-5 =6lastest0=minlastest1-dut01，lastest2-dut02 =min6-6,7-7 =0計算好每個事件的最早和最遲發(fā)生時間后，我們可以很容易地算出每個活動的最早和最遲開始時間，假設分別用actearliest和actlastest數(shù)組表示，設活動i的兩端事件分別為事件j和事件k,如下所示：活動i事件j 事件k則：actearliesti=earliestjactlastesti=lastestk-dutjk關

20、鍵路徑 對于上圖，用上述方法求得所有活動的最早和最遲開始時間如下表：活動活動 21 1424353743454 5 6 最早最早0 00 06 66 67 71414141411111111111116161414最遲最遲0 00 011116 67 71515141411111313121217171515余量余量0 00 05 50 00 01 10 00 02 21 11 11 1 上表中的余量（稱為開始時間余量）是該活動的最遲開始時間減去最早開始時間，余量不等于0的活動表示該活動不一定要在最早開始時間時就進行，可以拖延一定的余量時間再進行，也不會影響整個工程的完成。而余量等于0的活動必

21、須在最早開始時間時進行，而且在規(guī)定的工期內完成，否則將影響整個工程的完成。我們把開始時間余量為0的活動稱為“關鍵活動”，由關鍵活動所形成的從源點到匯點的每一條路徑稱為“關鍵路徑”。關鍵路徑 上圖所示的AOE網的關鍵路徑如下圖所示。細心的讀者可能已經發(fā)現(xiàn)，其實關鍵路徑就是從源點到匯點具有最大路徑長度的那些路徑。這很容易理解，因為整個工程的工期就是按照最長路徑計算出來的。很顯然，要想縮短整個工程的工期，就應該想法設法去縮短關鍵活動的持續(xù)時間。讀者可以根據上面的思想編程求出AOE網的關鍵路徑。上機練習 1、煩人的幻燈片【問題描述】李教授將于今天下午作一次非常重要的演講。不信的事他不是一個非常愛整潔的

22、人，他把自己演講要用的幻燈片隨便堆在了一起。因此，演講之前他不得不去整理這些幻燈片。作為一個講求效率的學者，他希望盡可能簡單地完成它。教授這次演講一共要用n n張幻燈片（n=26n=26），這n n張幻燈片按照演講要使用的順序已經用數(shù)字1n1n編了號。因為幻燈片是透明的，所以我們不能一下子看清每一個數(shù)字所對應的幻燈片。現(xiàn)在我們用大寫字母A,B,CA,B,C再次把幻燈片依次編號。你的任務是編寫一個程序，把幻燈片的數(shù)字編號和字母編號對應起來，顯然這種對應應該是唯一的；若出現(xiàn)多種對應的情況或是某些數(shù)字編號和字母編號對應不起來，我們稱對應是無法實現(xiàn)的?！据斎敫袷健课募牡谝恍兄挥幸粋€整數(shù)n n，表示有n張幻燈片，接下來的n n行每行包括4 4個整數(shù)xmin,xmax,ymin,ymaxxmin,xmax,ymin,ymax（整數(shù)之間用空格分開）為幻燈片的坐標，這n n張幻燈片按其在文件中出現(xiàn)的順序從前到后依次編號為A,B,CA,B,C，再接下來的n行依次為n n個數(shù)字編號的坐標x,yx,y，顯然在幻燈片之外是不會有數(shù)字的?！据敵龈袷健咳羰菍?/p>