關鍵路徑算法課程設計

1、曲曲2孽虎數(shù)據(jù)結構課程設計說明書題目：求網(wǎng)中的關鍵路徑班級計科1203組別：指導老師：彭代文元成時間：2014.6.6組長：王勛峰學19組員1:將磊學號：18組員2:劉源學號：17組員3:陳乙生學號：16成績：需求分析11.1 題目內容與要求11.2 題目理解與功能分析1概要設計23.1 設計思路23.2 系統(tǒng)模塊圖32.2系統(tǒng)模塊圖.3三詳細設計.4圖存儲結構的建立求取關鍵路徑.8主程序建立10四實驗結果.11五課程設計心得.12六參考文獻.13二附錄（程序清單）14一需求分析題目內容與要求內容：自擬定合適的方式，從鍵盤上輸入一個AOE網(wǎng)，并用合適的存儲結構存儲該AOE網(wǎng)，然后求出該AOE網(wǎng)

2、的關鍵路徑?；疽螅?輸入AOE網(wǎng)的方式要盡量的簡單方便；.要能夠較形象地觀察AOE網(wǎng)和它的關鍵路徑；.課程設計報告必須符合課程設計報告規(guī)范；.提交合格的課程設計報告，經(jīng)指導教師測試課設完成(驗收)程序，課設完成；題目理解與功能分析該題實質要求用數(shù)據(jù)結構中的圖形知識編寫一個求無循環(huán)有向帚權圖中從起點到終點所有路徑，經(jīng)分析、比較求出長度最大路徑，從而求出關鍵路徑。通常我們用有向圖表示一個工程。在這種有向圖中，用頂點表示活動，用有向邊Vi,Vj表示活動Vi必須先于活動Vj進行。如果在這種圖中用有向邊表示一個工程中的各項活動(ACTIVITY),用有向邊上的權值表示活動的持續(xù)時間(DURATION

3、),用頂點表示事件(EVENT),則這種的有向圖叫做用邊表示活動的網(wǎng)絡，簡稱AOE網(wǎng)絡。在AOE網(wǎng)絡中，從源點到各個頂點，可能不止一條。這些路徑的長度也可能不同。不同路徑所需的時間雖然不同，但只有各條路徑上所有活動都完成了，這個工程才算完成。因此，完成整個工程所需的時間取決于從源點到匯點的最長路徑長度，即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度就叫做關鍵路徑(criticalpath)。程序所要達到的功能：輸入并建立AOE網(wǎng)；輸出關鍵活動并求出這個工程的關鍵路徑；求出完成這個關鍵路徑的最少時間并輸出，該程序結束。二概要設計2.1設計思路基本設計思路：(1)以某一個求無循環(huán)有向帚權圖藍本

4、。(2)觀察并記錄這個圖中每個弧的起始點及權值。(3)用記錄的結果建立AOE網(wǎng)，即邊表示活動的網(wǎng)絡，并用圖的形式表示。(4)用領接表來存儲圖這些信息。(5)用CreateGraph()函數(shù)建立AOE圖。(6)用ChticalPath()函數(shù)求出最大路徑，并打印出關鍵路徑。(7)編寫代碼并測試。2.2系統(tǒng)模塊圖求關鍵路徑建立AOE網(wǎng)計算關鍵路徑主程序瑁加頂點拓撲徘序關鍵路徑調試函數(shù)圖2-1系統(tǒng)模塊圖三詳細設計圖存儲結構的建立全局變量及用途：#defineMAX_VERTEX_NUM50/最大頂點數(shù)intindegreeMAX_VERTEX_NUM;/存放節(jié)點入度數(shù)組intveMAX_VERTEX

5、_NUM,vlMAX_VERTEX_NUM;/頂點事件最早發(fā)生時間而最遲發(fā)生而問數(shù)組，全店變量初始為0inteeMAX_VERTEX_NUM,elMAX_VERTEX_NUM;/弧活動最早發(fā)生時間和最遲發(fā)生時間數(shù)組stack<int>S;/存放入度為0的結點stack<int>T;/存放頂點的拓撲序列先建立鄰接表的存儲單元，為建立鄰接表做準備。為圖中每個頂點建立一個單鏈表，第i個單鏈表中的結點表示依附于頂點vi的邊（對于有向圖是以vi為尾的弧）。每個結點由3個域組成，其中鄰接域（adjvex）指示與頂點vi鄰接的點在圖中的位置，鏈域（nextedge）f示下一條邊或弧的

6、結點，權值域（W）存儲邊或弧的權值大小。在表頭結點除了設有鏈域（firstedge）指向鏈表中第一個結點之外，還設有存儲頂點v或其他有關的數(shù)據(jù)域（data）和存儲頂點入度的域（id）（代碼如下）。數(shù)據(jù)存儲結構:typedefstructArcNode/結點結構(intadjvex;/該邊所指的頂點的位置structArcNode*nextarc;/指向下一條邊的指針I(yè)nforTypeinfo;/弧的長度(關鍵路徑中的活動)ArcNode;/表的結點typedefstructVNode/頂點(VertexTypedata;/頂點信息【如數(shù)據(jù)等】ArcNode*firstarc;/指向第一條依附該

7、頂點的邊的弧指針VNode;typedefstructALGraph(VNodeverticesMAX_VERTEX_NUM;/頂點線性表【數(shù)組】intvexnum,arcnum;/圖的當前頂點數(shù)和弧數(shù)ALGraph;構造有向圖。構圖函數(shù)由增加結點和增加邊構成。第一，增加結點：輸入頂點數(shù)級定點信息，并初始化該頂點的邊表。第二，首先輸入邊所依附的兩個頂點及權重，最后將該結點接到第i個表尾部。(代碼如下)定位函數(shù)：/=返回頂點v在頂點向量中的位置=intLocateVex(ALGraph*G,charv)(for(inti=1;v!=G->verticesi.data&&i&

8、lt;=G->vexnum;i+)if(i>G->vexnum)return0;returni;)/=構造令口接鏈表圖=voidCreateGraph(ALGraph*G)(add_vex(G);/增加節(jié)點add_arc(G);/增加邊)/=增力口邊=voidadd_arc(ALGraph*G)(ArcNode*s;ArcNode*p;cout<<"n輸入有向圖邊數(shù)："cin>>G->arcnum;charv1,v2;intlength;cout<<"nn輸入邊信息(始點終點權值)："<&

9、lt;endl;for(intk=1;k<=G->arcnum;k+)(cin>>v1>>v2>>length;inti=LocateVex(G,v1);intj=LocateVex(G,v2);/確定v1,v2在G中的位置indegreej+;/點j的入度增加1s=(ArcNode*)malloc(sizeof(ArcNode);s->adjvex=j;/該邊所指向的頂點的位置為js->info=length;s->nextarc=NULL;if(G->verticesi.firstarc=NULL)(G->ver

10、ticesi.firstarc=s;)else(for(p=G->verticesi.firstarc;p->nextarc!=NULL;p=p->nextarc)/尾插法構建頂點鏈表；p->nextarc=s;)3.2求取關鍵路徑利用AOE網(wǎng)進行工程管理時，需解決的兩個主要問題：其一，計算完成整個工程的最短工期；其二，確定關鍵路徑，以找出哪些活動時影響工程進度的關鍵。因此須計算以下幾點：(1)事件的最早發(fā)生時間vek;(2)事件最遲發(fā)生時間vlk；(3)活動最早開始時間eei；(4)活動的最遲開始時間eli;計算其過程必須分別在拓撲有序和逆拓撲有序的前提下進行。也就說

11、，vek必須在事件vk所有前驅的最早發(fā)生的時間求得之后才能確定。因此，可以在拓撲排序的基礎上計算vek和vlk。由此得到求解關鍵路徑的方法：首先輸入arcnum條有向邊<i,j>,建立AOE網(wǎng)的鄰接表存儲結構；然后從始點出發(fā)，令事件的最早發(fā)生時間為0,按拓撲有序求其余各頂點時間的最早發(fā)生時間vek；（代碼如下）If（vet+p->info>vek）vek=vet+p->info;/vekk（終點）頂點事件最早能發(fā)生的時間ve初始為0接著從終點出發(fā)，令事件最遲發(fā)生時間等于其最早發(fā)生時間，按你你逆拓撲排序求其余各頂點事件最遲發(fā)生時間vlk；最后根據(jù)各頂點事件的ve和v

12、l值，求所有活動最早開始時間ee和最遲開始時間el。如果某活動滿足條件ee=el,則為關鍵活動。(代碼如下)if(vlk-dut<vlt)vlt=vlk-dut;/vltt(始點)頂點事件最遲發(fā)生時間for(intj=1;j<=G->vexnum;j+)p=G->verticesj.firstarc;while(p)i+;intk=p->adjvex;eei=vej;eli=vlk-p->info;printf("|%3c|%3c|%6d|%6d|%3d|",G->verticesj.data,G->verticesk.dat

13、a,eei,eli,eli-eei);if(eli=eei)printf("此弧為關鍵活動");p=p->nextarc;同時，為計算各頂點事件的ve值是在拓撲排序的過程中進行的，因此需一個棧來記錄拓撲排序，如果頂點的入度為0,則該頂點入棧。intt=S.top();S.pop();T.push(t);count+;/度為0的結點出棧S入棧T棧T保存拓撲序列cout<<"關鍵路徑所需時間為："<<veG->vexnum;3.3主程序建立該部分主要是對所建立的函數(shù)的調用。包括：建立圖白函數(shù)CreateGraph()；計算

14、關鍵路徑的函數(shù)CriticalPath()；最后程序結束。這樣安排可以增強程序的可讀性，是程序便于理解，也便于日后的對程序的維護和修改等操作。四實驗結果按照要求輸入一組關于無循環(huán)有向帚權圖所有信息。如：6123456812301320242025303440363046205610依次執(zhí)行程序每一步，最后結束該程序程序運行如下圖：'DMicroEoftViuadi0'.,MyPrejects*.關鍵萼脛,-.Z)ebug'巨己強寫exe&rJa-r7gr>a-r?gsnr-123456有有有有有有步步步步步步-r-l二戶.r4-r-l二盧“F>77&

15、gt;77121211cccccC口口口yyV-yy方方方方方方2546>>>>-共有4種拓撲排序方式逆拓撲序列為：>6'>4>5>2>3>1'起點*終點'取早開始時間!最遲開始時間：差值：是否為關鍵路徑003830202060&010W4040205060701001B1003B010此弧為關鍵活動此弧為關鍵活動此弧為關鍵活動頂點事件:生生發(fā)發(fā)早退日譬取0088006?00660022003400:e1VU關鍵路徑為：一>1一>3一>4一>6關鍵路徑所需時間為；80五程序設計心

16、得通過這次求關鍵路徑，我對圖的鄰接表有了深刻的了解。以前都是用鄰接矩陣的，感覺鄰接矩陣直觀簡便，而這次關鍵路徑的有關算法，書上都是使用鄰接表的，我試著熟悉它，發(fā)現(xiàn)也挺好用的，許多操作用鄰接表更方便。書上沒有鄰接表的構圖代碼，拓撲排序，關鍵路徑的都是偽代碼，我不得不去查資料，思索，自己編寫完整可執(zhí)行的代碼，這個過程很艱辛，也很愉快。拓撲排序時我想辦法弄出了不同拓撲排序的總數(shù)，卻怎么也無法打印出所有的拓撲序列。在關鍵路徑求頂點事件最遲的發(fā)生時間時，錯把各個頂點的最早發(fā)生時間賦給了它，所以輸出的結果怎么都不對，我在這個地方糾結的好久。知識只有在使用的時候才會遠遠感覺不夠用，我深深體會到了這句話。這次

17、的程序設計對我的幫助很大，雖然真正自己寫的代碼并不多，許多都是書上的代碼經(jīng)過補充改寫的，但畢竟我都把這整個過程走了一遍，熟悉了圖的各種操作，各種算法我都認真看懂了，思考了。我能感覺到自己的進步，每次編寫出一個程序，在電腦上運行出來時，都會有一種莫名的成就感，很享受這種感覺，我會繼續(xù)努力的。計科1203王勛峰1嚴蔚敏編。數(shù)據(jù)結構（C語言版）。北京：清華大學出版社，1997.22譚浩強著。C語言程序設計（第二版）。北京：清華大出版社，2001.33武愛平編。C語言程序設計。長春：吉林大學出版社出版，2010.1七附錄（程序清單）程序可運行#include<iostream>usingn

18、amespacestd;#include<stack>typedefcharVertexType;typedefintVRType;typedefintInforType;#defineMAX_VERTEX_NUM50/最大頂點數(shù)intindegreeMAX_VERTEX_NUM;/存放節(jié)點入度數(shù)組intveMAX_VERTEX_NUM,vlMAX_VERTEX_NUM;/頂點事件最早發(fā)生時間和最遲發(fā)生時間數(shù)組，全局變量初始為0inteeMAX_VERTEX_NUM,elMAX_VERTEX_NUM;/弧活動最早發(fā)生時間和最遲發(fā)生時小數(shù)組stack<int>S;/存放入

19、度為0的結點stack<int>T;/存放頂點的拓撲序列/*/typedefstructArcNode/結點結構intadjvex;/該邊所指的頂點的位置structArcNode*nextarc;/指向下一條邊的指針I(yè)nforTypeinfo;ArcNode;typedefstructVNode(VertexTypedata;ArcNode*firstarc;針VNode;typedefstructALGraph(VNodevertices50;intvexnum,arcnum;/弧的長度（關鍵路徑中的活動）/表的結點/頂點/頂點信息【如數(shù)據(jù)等】/指向第一條依附該頂點的邊的弧指/

20、頂點線性表【數(shù)組】/圖的當前頂點數(shù)和弧數(shù)ALGraph;/*/=返回頂點v在頂點向量中的位置=intLocateVex(ALGraph*G,charv)(for(inti=1;v!=G->verticesi.data&&i<=G->vexnum;i+)Jif(i>G->vexnum)return0;returni;/=增加節(jié)點=voidadd_vex(ALGraph*G)(cout<<"n輸入有向圖頂點數(shù)："cin>>G->vexnum;cout<<"n輸入頂點信息："

21、;<<endl;for(inti=1;i<=G->vexnum;i+)(cin>>G->verticesi.data;/構造頂點向量G->verticesi.firstarc=NULL;/初始鏈指針/=增力口邊=voidadd_arc(ALGraph*G)(ArcNode*s;ArcNode*p;cout<<"n輸入有向圖邊數(shù)："cin>>G->arcnum;charv1,v2;intlength;cout<<"nn輸入邊信息(始點終點權值)："<<en

22、dl;for(intk=1;k<=G->arcnum;k+)(cin>>v1>>v2>>length;inti=LocateVex(G,v1);intj=LocateVex(G,v2);/確定v1,v2在G中的位置indegreej+;/點j的入度增加1s=(ArcNode*)malloc(sizeof(ArcNode);s->adjvex=j;/該邊所指向的頂點的位置為js->info=length;s->nextarc=NULL;if(G->verticesi.firstarc=NULL)G->verticesi

23、.firstarc=s;elsefor(p=G->verticesi.firstarc;p->nextarc!=NULL;p=p->nextarc)/尾插法構建頂點鏈表;p->nextarc=s;/=構造令口接鏈表圖=voidCreateGraph(ALGraph*G)add_vex(G);/增加節(jié)點add_arc(G);/增加邊:拓撲排序intTopologicalSort(ALGraph*G)(inta10;intcount=0;/count為入?！驹L問】頂點的計數(shù)ArcNode*p;for(inti=1;i<=G->vexnum;i+)(if(inde

24、greei=0)S.push(i);printf("n拓撲排序:n");i=1;while(!S.empty()(intt=S.top();a0=1;ai=ai-1*S.size();printf("n第%d步有(d)種方式",i,S.size();/棧內為度為0結點的【下標】i+;printf("->%c(%d)",G->verticest.data,t);S.pop();T.push(t);count+;/度為0的結點出棧S入棧T棧T保存拓撲序列for(p=G->verticest.firstarc;p;p=p-

25、>nextarc)/與度為0結點相鄰的結點的入度減1(intk=p->adjvex;indegreek-;if(indegreek=0)S.push(k);if(vet+p->info>vek)vek=vet+p->info;/vekk(終點)頂點事件最早能發(fā)生的時間ve初始為0printf("nn共有%d種拓撲排序方式n”,aG->vexnum);if(count<G->vexnum)return0;/若小于頂點數(shù)說明圖中有環(huán)elsereturn1;/=求關鍵路徑=voidCriticalPath(ALGraph*G)/G為有向網(wǎng)，輸

26、出G的各項關鍵活動(ArcNode*p;if(TopologicalSort(G)=0)(cout<<"n該圖有環(huán)!"for(inti=1;i<=G->vexnum;i+)/初始化頂點事件最初發(fā)生的事件為工程總時間(為一較大值)(vli=veG->vexnum;printf("n逆拓撲序列為：")；while(!T.empty()(intt=T.top();printf("->%c",G->verticest.data);T.pop();for(p=G->verticest.firsta

27、rc;p!=NULL;p=p->nextarc)(intk=p->adjvex;intdut=p->info;if(vlk-dut<vlt)vlt=vlk-dut;/vltt(始點)頂點事件最遲發(fā)生時間printf("nnn|起點|終點|最早開始時間|最遲開始時間|差值|是否為關鍵路徑nn");i=0;for(intj=1;j<=G->vexnum;j+)p=G->verticesj.firstarc;while(p)i+;intk=p->adjvex;eei=vej;eli=vlk-p->info;/printf("|%4c|%4c|%12d|%12d|%4d|",G->verticesj.data,G->verticesk.data,eei,eli,eli-eei);printf("|%3c|%3c|%6