關(guān)鍵路徑問(wèn)題

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)題目關(guān)鍵路徑問(wèn)題院系計(jì)算機(jī)系年級(jí)班級(jí)2016計(jì)科（嵌入）學(xué)生姓名陳銀學(xué)號(hào)20162375004學(xué)期2017-2018（二）任課教師黃群1引言2需求分析2.1問(wèn)題描述2.2基本要求2.3目的3概要設(shè)計(jì)3.1數(shù)據(jù)類(lèi)型3.2程序流程圖4詳細(xì)設(shè)計(jì)4.1創(chuàng)建圖的函數(shù)4.2求關(guān)鍵路徑5關(guān)鍵路徑測(cè)試6課程設(shè)計(jì)總結(jié)與體會(huì)7參考文獻(xiàn)1引言當(dāng)一項(xiàng)工程分為多個(gè)子工程時(shí)，需要確定這么子過(guò)程的次序問(wèn)題，還需要計(jì)算整個(gè)工程的時(shí)間，確定哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵，為按時(shí)或者提前完成整個(gè)工程提供保證，這就是關(guān)鍵路徑的問(wèn)題。關(guān)鍵路徑問(wèn)題相應(yīng)的網(wǎng)稱(chēng)為AOE網(wǎng)，其中：頂點(diǎn)表示事件，邊表示活動(dòng)，邊得權(quán)表示活動(dòng)持續(xù)時(shí)間，AOE網(wǎng)可以用來(lái)估算工程完成的時(shí)間。2需求分析2.1問(wèn)題描述（1）選擇建圖方法有:涉及鄰接矩陣，鄰接表，十字鏈表，鄰接多重等多種方法，要選擇一種適當(dāng)?shù)姆椒ńD，提高算法效率，降低時(shí)間復(fù)雜度和空間復(fù)雜度。（2）兩個(gè)相鄰頂點(diǎn)與它們之間的邊表示活動(dòng)，邊上的數(shù)據(jù)表示活動(dòng)延續(xù)的時(shí)間。對(duì)于給出的事件AOE網(wǎng)絡(luò)。要求求出從起點(diǎn)到終點(diǎn)的所有路徑，經(jīng)分析，比較后找出長(zhǎng)讀最大的路徑，從而得出關(guān)鍵路徑的算法，并給出計(jì)算機(jī)上機(jī)實(shí)現(xiàn)的源程序。完成不同路徑的活動(dòng)所需時(shí)間不同，但路徑各條上所有活動(dòng)都完成，這個(gè)工程才算完成。2.2基本要求1選擇一種算法建立圖：選擇鄰接表算法，是一種順序＋鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用順序表存放頂點(diǎn)，為每個(gè)頂點(diǎn)建立一個(gè)單鏈表，單鏈表中的結(jié)點(diǎn)表示該頂點(diǎn)的邊或以該頂點(diǎn)為尾的弧。2兩個(gè)相鄰頂點(diǎn)與它們之間邊表示活動(dòng)，邊上的數(shù)字表示活動(dòng)時(shí)間，求出從起點(diǎn)到終點(diǎn)的所有路徑，然后通過(guò)拓?fù)渑判蚝湍嫱負(fù)渑判蚯蟪鲎钤缗c最晚發(fā)生時(shí)間，找出長(zhǎng)度最大的路徑，從而求得關(guān)鍵路徑。2.3目的通過(guò)輸入所要構(gòu)造的圖頂點(diǎn)數(shù)，弧數(shù)，創(chuàng)建圖，并打印出來(lái)，對(duì)圖進(jìn)行拓?fù)渑判颍蟮么藞D最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間，并求得關(guān)鍵活動(dòng)和關(guān)鍵路徑。3概要設(shè)計(jì)求關(guān)鍵路徑必須在拓?fù)渑判虻那疤嵯?，有環(huán)圖不能求關(guān)鍵路徑，只能減少關(guān)鍵活動(dòng)工期，只有在不改變關(guān)鍵路徑的前提下，減少關(guān)鍵活動(dòng)才能減少整個(gè)工期。活動(dòng)最早時(shí)間ve(i);最晚時(shí)間vi（i）。3.1數(shù)據(jù)類(lèi)型structGraphNode{intstart;//弧尾的頂點(diǎn)的下標(biāo)intend;//弧頭的頂點(diǎn)的下標(biāo)，有箭頭的一方intweight;//弧的權(quán)重GraphNode*next;//下一條弧};//頭結(jié)點(diǎn)structPnode{GraphNode*firstarc;//第一條依附在該頂點(diǎn)的弧stringdata;};3.2程序流程圖開(kāi)始開(kāi)始主函數(shù)：求關(guān)鍵主函數(shù)：求關(guān)鍵文件輸入文件輸入求最大路徑，打印關(guān)鍵路徑結(jié)束求最大路徑，打印關(guān)鍵路徑結(jié)束4詳細(xì)設(shè)計(jì)4.1創(chuàng)建圖的函數(shù)classGraph_DG{private:intapex;//頂點(diǎn)個(gè)數(shù)intedge;//邊的條數(shù)Pnode*arc;//鄰接表int*indegree;//各個(gè)頂點(diǎn)的入度情況stack<int>List;//拓?fù)湫蛄兄懈鱾€(gè)邊的情況int*ve;//記錄每個(gè)頂點(diǎn)的最早發(fā)生時(shí)間int*vl;//記錄每個(gè)頂點(diǎn)最遲發(fā)生時(shí)間public:Graph_DG(intapex,intedge);~Graph_DG();//析構(gòu)函數(shù)boolcheck_edge_value(int,int,int);//檢查邊的信息是否合法voidcreateGraph();//創(chuàng)建一個(gè)新的圖voidprint();//打印圖的鄰接表booltopological_sort();boolCriticalPath();};4.2求關(guān)鍵路徑#include"關(guān)鍵路徑.h"Graph_DG::Graph_DG(intapex,intedge){/*初始化一些基本的信息，包括邊和頂點(diǎn)個(gè)數(shù)，各個(gè)頂點(diǎn)入度數(shù)組，鄰接表的等*/this->apex=apex;this->edge=edge;this->arc=newPnode[this->apex];this->indegree=newint[this->apex];this->ve=newint[this->apex];this->vl=newint[this->apex];for(inti=0;i<this->apex;i++){this->indegree[i]=0;this->ve[i]=0;this->arc[i].firstarc=NULL;this->arc[i].data="v"+to_string(i+1);}}//釋放內(nèi)存空間Graph_DG::~Graph_DG(){GraphNode*p,*q;for(inti=0;i<this->apex;i++){if(this->arc[i].firstarc){p=this->arc[i].firstarc;while(p){q=p->next;deletep;p=q;}}}delete[]this->arc;delete[]this->indegree;}//判斷我們每次輸入的的邊的信息是否合法//頂點(diǎn)從1開(kāi)始編號(hào)boolGraph_DG::check_edge_value(intstart,intend,intweight){if(start<1||end<1||start>apex||end>apex||weight<0){returnfalse;}returntrue;}voidGraph_DG::createGraph(){cout<<"請(qǐng)輸入每條邊的起點(diǎn)和終點(diǎn)的編號(hào)（頂點(diǎn)從1開(kāi)始編號(hào)）以及每條邊的權(quán)重"<<endl;intcount=0;//記錄初始化邊的條數(shù)intstart,end,weight;while(count!=this->edge){cin>>start>>end>>weight;while(!check_edge_value(start,end,weight)){cout<<"輸入的信息不合法，請(qǐng)重新輸入："<<endl;cin>>start>>end>>weight;}GraphNode*temp=newGraphNode;temp->start=start-1;temp->end=end-1;temp->weight=weight;temp->next=NULL;//如果當(dāng)前頂點(diǎn)的還沒(méi)有邊依附時(shí)，++indegree[temp->end];//對(duì)應(yīng)的弧頭的頂點(diǎn)的入度加1if(this->arc[start-1].firstarc==NULL){this->arc[start-1].firstarc=temp;}else{GraphNode*now=this->arc[start-1].firstarc;while(now->next){now=now->next;}//找到該鏈表的最后一個(gè)結(jié)點(diǎn)now->next=temp;}++count;}}voidGraph_DG::print(){cout<<"圖的鄰接表為："<<endl;intcount=0;while(count!=this->apex){cout<<this->arc[count].data<<"";GraphNode*temp=this->arc[count].firstarc;while(temp){cout<<"<"<<this->arc[temp->start].data<<","<<this->arc[temp->end].data<<">="<<temp->weight<<"";temp=temp->next;}cout<<"^"<<endl;++count;}}boolGraph_DG::topological_sort(){cout<<"圖的拓?fù)湫蛄袨椋?<<endl;stack<int>s;//保存入度為0的頂點(diǎn)下標(biāo)GraphNode*temp;inti;for(i=0;i<this->apex;i++){if(!indegree[i])s.push(i);//入度為0，則入棧}//count用于計(jì)算輸出的頂點(diǎn)個(gè)數(shù)intcount=0;while(!s.empty()){//如果棧為空，退出循環(huán)i=s.top();//i等于棧頂?shù)脑豷.pop();cout<<this->arc[i].data<<"";//輸出拓?fù)湫蛄衪emp=this->arc[i].firstarc;this->List.push(i);while(temp){if(!(--indegree[temp->end])){//如果入度減少到為0，則入棧s.push(temp->end);}//同時(shí)更新ve的值if((ve[i]+temp->weight)>ve[temp->end]){ve[temp->end]=ve[i]+temp->weight;}temp=temp->next;}++count;}if(count==this->apex){cout<<endl;returntrue;}cout<<"此圖有環(huán)，無(wú)拓?fù)湫蛄?<<endl;returnfalse;//說(shuō)明這個(gè)圖有環(huán)}boolGraph_DG::CriticalPath(){if(!this->topological_sort()){cout<<"此圖有環(huán)，無(wú)關(guān)鍵路徑"<<endl;returnfalse;}cout<<"圖的關(guān)鍵路徑為："<<endl;//初始化vl的值都為ve[this->vexnum-1]intk;for(k=0;k<this->apex;k++){vl[k]=ve[this->apex-1];}GraphNode*temp;while(!this->List.empty()){k=List.top();//從逆拓?fù)渑判蜷_(kāi)始，求vlList.pop();temp=this->arc[k].firstarc;while(temp){//dut<k,temp->end>，從以第k個(gè)頂點(diǎn)為弧尾集合中選擇一個(gè)最小的值//來(lái)作為第i個(gè)頂點(diǎn)的最遲發(fā)生時(shí)間if(vl[k]>(vl[temp->end]-temp->weight)){vl[k]=vl[temp->end]-temp->weight;}temp=temp->next;}}intee;intel;for(k=0;k<this->apex;k++){temp=temp=this->arc[k].firstarc;while(temp