關(guān)鍵路徑問題

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