關(guān)鍵路徑算法課程設(shè)計

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

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

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

4、。(2)觀察并記錄這個圖中每個弧的起始點及權(quán)值。(3)用記錄的結(jié)果建立AOE網(wǎng)，即邊表示活動的網(wǎng)絡(luò)，并用圖的形式表示。(4)用領(lǐng)接表來存儲圖這些信息。(5)用CreateGraph()函數(shù)建立AOE圖。(6)用ChticalPath()函數(shù)求出最大路徑，并打印出關(guān)鍵路徑。(7)編寫代碼并測試。2.2系統(tǒng)模塊圖求關(guān)鍵路徑建立AOE網(wǎng)計算關(guān)鍵路徑主程序瑁加頂點拓?fù)渑切蜿P(guān)鍵路徑調(diào)試函數(shù)圖2-1系統(tǒng)模塊圖三詳細(xì)設(shè)計圖存儲結(jié)構(gòu)的建立全局變量及用途：#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的結(jié)點stack<int>T;/存放頂點的拓?fù)湫蛄邢冉⑧徑颖淼拇鎯卧?，為建立鄰接表做?zhǔn)備。為圖中每個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點表示依附于頂點vi的邊（對于有向圖是以vi為尾的?。?。每個結(jié)點由3個域組成，其中鄰接域（adjvex）指示與頂點vi鄰接的點在圖中的位置，鏈域（nextedge）f示下一條邊或弧的

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

7、頂點的邊的弧指針VNode;typedefstructALGraph(VNodeverticesMAX_VERTEX_NUM;/頂點線性表【數(shù)組】intvexnum,arcnum;/圖的當(dāng)前頂點數(shù)和弧數(shù)ALGraph;構(gòu)造有向圖。構(gòu)圖函數(shù)由增加結(jié)點和增加邊構(gòu)成。第一，增加結(jié)點：輸入頂點數(shù)級定點信息，并初始化該頂點的邊表。第二，首先輸入邊所依附的兩個頂點及權(quán)重，最后將該結(jié)點接到第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;)/=構(gòu)造令口接鏈表圖=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輸入邊信息(始點終點權(quán)值)："<&

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)/尾插法構(gòu)建頂點鏈表；p->nextarc=s;)3.2求取關(guān)鍵路徑利用AOE網(wǎng)進(jìn)行工程管理時，需解決的兩個主要問題：其一，計算完成整個工程的最短工期；其二，確定關(guān)鍵路徑，以找出哪些活動時影響工程進(jìn)度的關(guān)鍵。因此須計算以下幾點：(1)事件的最早發(fā)生時間vek;(2)事件最遲發(fā)生時間vlk；(3)活動最早開始時間eei；(4)活動的最遲開始時間eli;計算其過程必須分別在拓?fù)溆行蚝湍嫱負(fù)溆行虻那疤嵯逻M(jìn)行。也就說

11、，vek必須在事件vk所有前驅(qū)的最早發(fā)生的時間求得之后才能確定。因此，可以在拓?fù)渑判虻幕A(chǔ)上計算vek和vlk。由此得到求解關(guān)鍵路徑的方法：首先輸入arcnum條有向邊<i,j>,建立AOE網(wǎng)的鄰接表存儲結(jié)構(gòu)；然后從始點出發(fā)，令事件的最早發(fā)生時間為0,按拓?fù)溆行蚯笃溆喔黜旤c時間的最早發(fā)生時間vek；（代碼如下）If（vet+p->info>vek）vek=vet+p->info;/vekk（終點）頂點事件最早能發(fā)生的時間ve初始為0接著從終點出發(fā)，令事件最遲發(fā)生時間等于其最早發(fā)生時間，按你你逆拓?fù)渑判蚯笃溆喔黜旤c事件最遲發(fā)生時間vlk；最后根據(jù)各頂點事件的ve和v

12、l值，求所有活動最早開始時間ee和最遲開始時間el。如果某活動滿足條件ee=el,則為關(guān)鍵活動。(代碼如下)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("此弧為關(guān)鍵活動");p=p->nextarc;同時，為計算各頂點事件的ve值是在拓?fù)渑判虻倪^程中進(jìn)行的，因此需一個棧來記錄拓?fù)渑判?，如果頂點的入度為0,則該頂點入棧。intt=S.top();S.pop();T.push(t);count+;/度為0的結(jié)點出棧S入棧T棧T保存拓?fù)湫蛄衏out<<"關(guān)鍵路徑所需時間為："<<veG->vexnum;3.3主程序建立該部分主要是對所建立的函數(shù)的調(diào)用。包括：建立圖白函數(shù)CreateGraph()；計算

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

15、gt;77121211cccccC口口口yyV-yy方方方方方方2546>>>>-共有4種拓?fù)渑判蚍绞侥嫱負(fù)湫蛄袨椋?gt;6'>4>5>2>3>1'起點*終點'取早開始時間!最遲開始時間：差值：是否為關(guān)鍵路徑003830202060&010W4040205060701001B1003B010此弧為關(guān)鍵活動此弧為關(guān)鍵活動此弧為關(guān)鍵活動頂點事件:生生發(fā)發(fā)早退日譬取0088006?00660022003400:e1VU關(guān)鍵路徑為：一>1一>3一>4一>6關(guān)鍵路徑所需時間為；80五程序設(shè)計心

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

17、的程序設(shè)計對我的幫助很大，雖然真正自己寫的代碼并不多，許多都是書上的代碼經(jīng)過補充改寫的，但畢竟我都把這整個過程走了一遍，熟悉了圖的各種操作，各種算法我都認(rèn)真看懂了，思考了。我能感覺到自己的進(jìn)步，每次編寫出一個程序，在電腦上運行出來時，都會有一種莫名的成就感，很享受這種感覺，我會繼續(xù)努力的。計科1203王勛峰1嚴(yán)蔚敏編。數(shù)據(jù)結(jié)構(gòu)（C語言版）。北京：清華大學(xué)出版社，1997.22譚浩強著。C語言程序設(shè)計（第二版）。北京：清華大出版社，2001.33武愛平編。C語言程序設(shè)計。長春：吉林大學(xué)出版社出版，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的結(jié)點stack<int>T;/存放頂點的拓?fù)湫蛄?*/typedefstructArcNode/結(jié)點結(jié)構(gòu)intadjvex;/該邊所指的頂點的位置structArcNode*nextarc;/指向下一條邊的指針I(yè)nforTypeinfo;ArcNode;typedefstructVNode(VertexTypedata;ArcNode*firstarc;針VNode;typedefstructALGraph(VNodevertices50;intvexnum,arcnum;/弧的長度（關(guān)鍵路徑中的活動）/表的結(jié)點/頂點/頂點信息【如數(shù)據(jù)等】/指向第一條依附該頂點的邊的弧指/

20、頂點線性表【數(shù)組】/圖的當(dāng)前頂點數(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òu)造頂點向量G->verticesi.firstarc=NULL;/初始鏈指針/=增力口邊=voidadd_arc(ALGraph*G)(ArcNode*s;ArcNode*p;cout<<"n輸入有向圖邊數(shù)："cin>>G->arcnum;charv1,v2;intlength;cout<<"nn輸入邊信息(始點終點權(quán)值)："<<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)/尾插法構(gòu)建頂點鏈表;p->nextarc=s;/=構(gòu)造令口接鏈表圖=voidCreateGraph(ALGraph*G)add_vex(G);/增加節(jié)點add_arc(G);/增加邊:拓?fù)渑判騣ntTopologicalSort(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拓?fù)渑判?n");i=1;while(!S.empty()(intt=S.top();a0=1;ai=ai-1*S.size();printf("n第%d步有(d)種方式",i,S.size();/棧內(nèi)為度為0結(jié)點的【下標(biāo)】i+;printf("->%c(%d)",G->verticest.data,t);S.pop();T.push(t);count+;/度為0的結(jié)點出棧S入棧T棧T保存拓?fù)湫蛄衒or(p=G->verticest.firstarc;p;p=p-

25、>nextarc)/與度為0結(jié)點相鄰的結(jié)點的入度減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種拓?fù)渑判蚍绞絥”,aG->vexnum);if(count<G->vexnum)return0;/若小于頂點數(shù)說明圖中有環(huán)elsereturn1;/=求關(guān)鍵路徑=voidCriticalPath(ALGraph*G)/G為有向網(wǎng)，輸

26、出G的各項關(guān)鍵活動(ArcNode*p;if(TopologicalSort(G)=0)(cout<<"n該圖有環(huán)!"for(inti=1;i<=G->vexnum;i+)/初始化頂點事件最初發(fā)生的事件為工程總時間(為一較大值)(vli=veG->vexnum;printf("n逆拓?fù)湫蛄袨椋?quot;)；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|起點|終點|最早開始時間|最遲開始時間|差值|是否為關(guān)鍵路徑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