求關(guān)鍵路徑設(shè)計(jì)報(bào)告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)畢業(yè)設(shè)計(jì)word格式-資料下載頁(yè)
2024-12-02 06:44本頁(yè)面
【導(dǎo)讀】的路徑，合理的安排非關(guān)鍵任務(wù)的施工順序。問(wèn)題要求寫一個(gè)程序從有向網(wǎng)中的某一頂點(diǎn)。出發(fā)找出該頂點(diǎn)到其余各頂點(diǎn)的最短路徑。③當(dāng)頂點(diǎn)i和j有邊，且其權(quán)值為Wij時(shí)，cost[i][j]=Wij。由于題目中沒(méi)有規(guī)定輸出格式，此程序以頂點(diǎn)序號(hào)的形式將最短路徑輸出到終端上去，深度優(yōu)先遍歷圖;對(duì)圖進(jìn)行拓?fù)渑判颍淮怂惴ò丫W(wǎng)中所有的頂點(diǎn)分成兩組，分別用S和T表示。已經(jīng)確定了最短路徑的終點(diǎn)屬于第一組S，S的初態(tài)應(yīng)只包含i0。另一組T則是尚未確定最。長(zhǎng)度始終不大于從i0到T中各頂點(diǎn)的路徑長(zhǎng)度。它的初始狀態(tài)即是鄰接矩陣cost中第i0列。顯然，從源點(diǎn)到各頂點(diǎn)的最短路徑中最短的一條路徑應(yīng)為。T中刪除后再并入S。依次類推，就能求出所需的最短路徑長(zhǎng)度。
【正文】 計(jì)算圖中每個(gè)頂點(diǎn)的入度 { for(int j=0。j20。++j) { b[j]=0。 } for(int i=0。i。++i) { Arode *p。 for(p=[i].firstarc。p。p=pnextarc) //循環(huán)每個(gè)頂點(diǎn)的出邊 { ++b[padjvex]。 //計(jì)算每個(gè)頂點(diǎn)的入度 } } } void TopologicalSort(ALGraph amp。G) { 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 15 int indegree[MAX]。 FindIngree(G,indegree)。 Sqstack S。 Inist_stack(S)。 for(int j=0。j。++j) { if(!indegree[j])push(S,j)。 } int count=0。 coutendl圖的拓?fù)渑判驗(yàn)?:。 while(StackEmpty(S)) //判斷棧非空就循環(huán) { int d。 d=pop(S)。 //出棧 coutd 。 //輸出頂點(diǎn) count++。 for(Arode *q=[d].firstarc。q。q=qnextarc) //循環(huán)所有頂點(diǎn)的出邊 { int k。 k=qadjvex。 if(!(indegree[k])) { push(S,k)。 //入度為零就入棧 } } } coutendl。 if(count) cout有環(huán) 。 } ////////////////////求關(guān)鍵路徑 int ve[MAX],vl[MAX]。 int TopologicalOrder(ALGraph G,Sqstack amp。T) { int indegree[MAX]。 FindIngree(G,indegree)。 Sqstack S。 Inist_stack(S)。 Inist_stack(T)。 for(int j=0。j。++j) { if(!indegree[j])push(S,j)。 //入度為零就入棧 } int count=0。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 16 for(int i=0。i。++i) ve[i]=0。 while(StackEmpty(S)) //棧非空就循環(huán) { int e。 e=pop(S)。 push(T,e)。 ++count。 Arode *q。 for(q=[e].firstarc。q。q=qnextarc) //循環(huán)一個(gè)頂點(diǎn)的所有出邊 { int k。 k=qadjvex。 if(!(indegree[k])) //判斷入度是否為零 { push(S,k)。 //為零入棧 } if(ve[e]+(qinfo)ve[k]) { ve[k]=ve[e]+(qinfo)。 } } } if(count) return 0。 //圖有環(huán) else return 1。 //無(wú)環(huán) } void Criticalpath(ALGraph amp。G) { Sqstack T。 if(!TopologicalOrder(G,T))couterrorendl。 //判斷圖是否為有環(huán) for(int i=0。i。++i) { vl[i]=ve[]。 //把每個(gè)頂點(diǎn)的最遲發(fā)生時(shí)間初始化為最后完成時(shí)間 } while(StackEmpty(T)) //棧非空就循環(huán) { int j。 j=pop(T)。 //出棧 for(Arode *p=[j].firstarc。p。p=pnextarc) { int k=padjvex。 int dut=pinfo。 //權(quán)值 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 17 if(vl[k]dutvl[j])vl[j]=vl[k]dut。 //各點(diǎn)的最遲發(fā)生時(shí)間 } } cout輸出為 (i1,i2,i3,i4,i5,i6)i1,i2 為邊， i3 為權(quán)值， i4 為最早發(fā)生時(shí)間， i5 為最遲發(fā)生時(shí)間 ,帶 39。*39。的是關(guān)鍵路徑 :endl。 Arode *p。 for(int j1=0。j1。++j1) { for(p=[j1].firstarc。p。p=pnextarc) { int k=padjvex。 int dut=pinfo。 int ee,el。 ee=ve[j1]。 el=vl[k]dut。 char tag。 if(ee==el) tag=39。*39。 //最早發(fā)生時(shí)間等于最遲發(fā)生時(shí)間 else tag=39。39。 //最早發(fā)生時(shí)間不等于最遲發(fā)生時(shí)間 coutj1 k dut ee el tagendl。 } } } void main() { ALGraph G。 Creat_ALGraph(G)。 //創(chuàng)建一個(gè)帶權(quán)的有向無(wú)環(huán)圖 DFSTraverse(G)。 //深度優(yōu)先遍歷 TopologicalSort(G)。 //拓?fù)渑判? Criticalpath(G)。 //求關(guān)鍵路徑 } 六． 心得 在這次編程的過(guò)程中，雖然經(jīng)歷的很多困難，但最終我都克服了，這給了我在以后的編程過(guò)程中戰(zhàn)勝困難的信心。通過(guò)這次編程，使我的編程經(jīng)驗(yàn)有所增加，鍛煉了我的編程能力，使我學(xué)到了很多的東西。
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1