求關(guān)鍵路徑設(shè)計報告 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計畢業(yè)設(shè)計word格式-預(yù)覽頁
【正文】 void DFSTraverse(ALGraph amp。T)； ／／若Ｇ無回路，則用棧Ｔ返回Ｇ的一個拓?fù)渑判蛄?，且函?shù)值為１，否則為０； void Criticalpath(ALGraph amp。 int StackEmpty(Sqstack amp。 int pop(Sqstack amp。 //創(chuàng)建一個帶權(quán)的有向無環(huán)圖 DFSTraverse(G)。G) { //創(chuàng) 建一個鄰接表結(jié)構(gòu)的圖 cin。++i) { [i].data=i。j。 padjvex=w。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 6 } }//Creat_ALGraph void Inist_stack(Sqstack amp。 //棧的大小 }//Inist_stack int StackEmpty(Sqstack amp。S,int a) { //把元素 a 放入棧 if() //棧沒有滿 { *=a。 }//push int pop(Sqstack amp。G,int v) { //從第 v 個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖 G visited[v]=1。q。 } }//DFS void DFSTraverse(ALGraph amp。 //把所有頂點表示成未訪問 } for(int j1=0。j20。++i) { Arode *p。 //各點入度加一 } } }//FindIngree void TopologicalSort(ALGraph amp。 Inist_stack(S)。 //入度為零的入棧 } int count=0。 //輸出頂點 count++。 k=qadjvex。 }// TopologicalSort int ve[MAX],vl[MAX]。 //初始化每個結(jié)點的入度 Sqstack S。j。i。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 9 push(T,e)。q。 } //入度為零的頂點放入棧 if(ve[e]+(qinfo)ve[k]) { ve[k]=ve[e]+(qinfo)。G) { //輸出圖 G 的關(guān)鍵路徑 Sqstack T。++i) { vl[i]=ve[]。p。 } //計算各頂點的最遲發(fā)生時間 } Arode *p。p。 ee=ve[j1]。*39。 } } }// Criticalpath 1. 函數(shù)的調(diào)用關(guān)系圖 Dijkstra 算法描述如下： （ 1） 輸入頂點個數(shù) n、鄰接矩陣 cost 和源點序號 i0； （ 2） 送初值：將 i0 加入第一組 S；令 dist[i]=cost[i0][i]； (i=1,2,… ,n)； （ 3） 重復(fù) n1 次做： ? 在不屬于 S 的頂點 U 中，選取具有最小 dist[u]值的頂點 v； ? 將 v 加入 S； ? 對不屬于 S 的頂點 U 做 dist[u]=min{dist[u], dist[v]+cost[v][u]}。 四． 程序分析調(diào)試，測試結(jié)果 １ . 分析調(diào)試 該程序用鄰接表存儲結(jié)構(gòu)，能夠節(jié)省存儲空間。 //指向下一個頂點的指針 int info。 //指向頂點的指針 }Vnode,Adjlist[MAX]。 }ALGraph。 cout請輸入邊數(shù) :。++i) { [i].data=i。 for(int j=0。 //輸入邊的兩個頂點和權(quán)值 p=new Arode。 [v].firstarc=p。 void Inist_stack(Sqstack amp。 } int StackEmpty(Sqstack amp。S,int a) //入棧 { if() { *=a。 return *。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 14 void DFSTraverse(ALGraph amp。 } for(int j1=0。G,int v) //從第 v 個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖 G { visited[v]=1。q。 } } //拓?fù)渑判? void FindIngree(ALGraph G,int b[20]) //計算圖中每個頂點的入度 { for(int j=0。i。p=pnextarc) //循環(huán)每個頂點的出邊 { ++b[padjvex]。 Sqstack S。++j) { if(!indegree[j])push(S,j)。 d=pop(S)。q。 //入度為零就入棧 } } } coutendl。T) { int indegree[MAX]。 Inist_stack(T)。 //入度為零就入棧 } int count=0。 while(StackEmpty(S)) //棧非空就循環(huán) { int e。 Arode *q。 k=qadjvex。 //圖有環(huán) else return 1。 //判斷圖是否為有環(huán) for(int i=0。 j=pop(T)。 int dut=pinfo。的是關(guān)鍵路徑 :endl。++j1) { for(p=[j1].firstarc。 int ee,el。 if(ee==el) tag=39。 //最早發(fā)生時間不等于最遲發(fā)生時間 coutj1 k dut ee el tagendl。 //深度優(yōu)先遍歷 TopologicalSort(G)。
公司管理相關(guān)推薦
鄂ICP備17016276號-1