求關(guān)鍵路徑設(shè)計(jì)報(bào)告 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)畢業(yè)設(shè)計(jì)（論文）

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目：關(guān)鍵路徑的設(shè)計(jì)報(bào)告科系：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：姓名：題目：1、編寫拓?fù)渑判蚝颓箨P(guān)鍵路徑的程序2、單源頂點(diǎn)最短路徑問題設(shè)計(jì)報(bào)告一 需求分析1. 在實(shí)際工程中拓?fù)渑判蚝颓箨P(guān)鍵路徑是經(jīng)常使用來安排任務(wù)的先后順序，以及找出關(guān)鍵的路徑，合理的安排非關(guān)鍵任務(wù)的施工順序。2.對(duì)用鄰接矩陣表示的有向圖，從某一頂點(diǎn)出發(fā)（稱為源點(diǎn)）到該圖其它各頂點(diǎn)（稱為終點(diǎn)）有無路徑？最短路徑是什么？路徑長(zhǎng)為多少？問題要求寫一個(gè)程序從有向網(wǎng)中的某一頂點(diǎn)出發(fā)找出該頂點(diǎn)到其余各頂點(diǎn)的最短路徑。對(duì)鄰接矩陣costnn中的每一個(gè)元素只能有三種情況： 當(dāng)i=j時(shí)，costij=0； 當(dāng)頂點(diǎn)i和j無邊時(shí)，costij=

2、； 當(dāng)頂點(diǎn)i和j有邊，且其權(quán)值為wij時(shí)，costij=wij。由于題目中沒有規(guī)定輸出格式，此程序以頂點(diǎn)序號(hào)的形式將最短路徑輸出到終端上去，并輸出該最短路徑的長(zhǎng)度。二 概要設(shè)計(jì)1.1抽象數(shù)據(jù)類型圖的定義如下：adt graph數(shù)據(jù)對(duì)象v:v是具有相同特性的數(shù)據(jù)元素的集合,稱為頂點(diǎn)集.數(shù)據(jù)對(duì)象i:i是具有相同特性的數(shù)據(jù)元素的集合,稱為頂點(diǎn)集.數(shù)據(jù)關(guān)系r: r=vr vr=(v,w)|v,w屬于v,(v,w)表示v和w之間存在路徑基本操作p: creat_algraph(&g,v,vr,i) 初始條件:v是圖的頂點(diǎn)集，vr是圖中邊的集合,i是邊的權(quán)值。 操作結(jié)果:按v和vr的定義構(gòu)造圖g。 dfs

3、(&g, v) 初始條件:v是圖的一個(gè)頂點(diǎn)，圖g存在。 操作結(jié)果:從v點(diǎn)深度優(yōu)先遍歷圖g。 dfstraverse(&g) 初始條件:圖g存在。 操作結(jié)果：深度優(yōu)先遍歷圖g。 findingree( g,b) 初始條件：圖g存在，數(shù)組b已知。 操作結(jié)果:圖g的每個(gè)頂點(diǎn)的度放在數(shù)組b中。 topologicalsort(&g) 初始條件:圖g存在。 操作結(jié)果:對(duì)圖g進(jìn)行拓?fù)渑判颉?topologicalorder(g,&t) 初始條件:圖g存在，棧t存在。 操作結(jié)果:若g無回路，則用棧t返回g的一個(gè)拓?fù)渑判蛄?，且函?shù)值為ok,否則為error. criticalpath(&g) 初始條件:g存在

4、，函數(shù)topologicalorder(g,&t)在。 操作結(jié)果:輸出圖g的關(guān)鍵路徑。adt graph1.2主程序void main( ) 圖的初始化; 創(chuàng)建一個(gè)圖; 深度優(yōu)先遍歷圖;對(duì)圖進(jìn)行拓?fù)渑判?；求關(guān)鍵路徑;2.1主要算法基本思想。單源最短路徑問題采用迪杰斯特拉（dijkstra）提出的按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑的算法。此算法把網(wǎng)中所有的頂點(diǎn)分成兩組，分別用s和t表示。凡是以i0為源點(diǎn)，已經(jīng)確定了最短路徑的終點(diǎn)屬于第一組s，s的初態(tài)應(yīng)只包含i0。另一組t則是尚未確定最短路徑的頂點(diǎn)集合。t的初態(tài)應(yīng)是除源點(diǎn)外的網(wǎng)中所有頂點(diǎn)的集合，按各頂點(diǎn)與i0間的最短路徑的長(zhǎng)度遞增的次序，逐個(gè)把t中

5、的頂點(diǎn)加入到s中，使得從i0到s中各頂點(diǎn)的路徑長(zhǎng)度始終不大于從i0到t中各頂點(diǎn)的路徑長(zhǎng)度。它的初始狀態(tài)即是鄰接矩陣cost中第i0列內(nèi)各列的值。顯然，從源點(diǎn)到各頂點(diǎn)的最短路徑中最短的一條路徑應(yīng)為 distv=mindisti(i=1,2,n)第一次求的最短路徑長(zhǎng)度必然是(i0,v)，這時(shí)頂點(diǎn)號(hào)v應(yīng)從t中刪除而并入s。每當(dāng)選出一個(gè)頂點(diǎn)號(hào)v并使之并入s后，就要修改t中各頂點(diǎn)的最短路徑長(zhǎng)度dist。對(duì)于t中的某一個(gè)頂點(diǎn)i來說，其最短路徑長(zhǎng)度或者仍是(i0,i)，或者是(i0,v,i)，決不可能有其它選擇，也就是說，若distv+costvig.vernum; /輸入頂點(diǎn)數(shù)cing.arcnum; /

6、輸入邊數(shù) for(int i=0;ig.vernum;+i)g.verticesi.data=i;g.verticesi.firstarc=null; /頂點(diǎn)初始化arcnode *p; /定義一個(gè)結(jié)點(diǎn)指針pfor(int j=0;jvwu; /輸入帶權(quán)的邊p=new arcnode;p-adjvex=w;p-info=u;p-nextarc=g.verticesv.firstarc;g.verticesv.firstarc=p;/creat_algraphvoid inist_stack(sqstack &s) /初始化棧s.base=new int(max); /為棧分配一個(gè)max大的空間

7、s.top=s.base; /棧頂?shù)扔跅５譻.stacksize=max; /棧的大小/inist_stackint stackempty(sqstack &s) /判斷棧是否為空if(s.base=s.top) /棧頂?shù)扔跅５?，則為空，返回0；return 0;elsereturn 1; /否則返回1；/stackemptyvoid push(sqstack &s,int a) /把元素a放入棧if(s.top-s.bases.stacksize) /棧沒有滿*s.top=a;+s.top;else /棧已滿在分配空間*s.top=a;+s.top;/pushint pop(sqstack

8、&s) /返回棧頂?shù)闹礽f(s.top!=s.base) /棧不為空-s.top;return *s.top;/popvoid dfs(algraph &g,int v) /從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖gvisitedv=1; /已被訪問coutvnextarc)int u;u=q-adjvex;if(!visitedu)dfs(g,u);/dfsvoid dfstraverse(algraph &g) /深度優(yōu)先遍歷圖gfor(int i1=0;i1g.vernum;+i1)visitedi1=0; /把所有頂點(diǎn)表示成未訪問for(int j1=0;j1g.vernum;+j1)if

9、(!visitedj1)dfs(g,j1); /沒有訪問就調(diào)用函數(shù)dfs/dfstraversevoid findingree(algraph g,int b20) /計(jì)算圖中每個(gè)頂點(diǎn)的入度for(int j=0;j20;+j)bj=0; /把數(shù)組全部置零for(int i=0;inextarc)+bp-adjvex; /各點(diǎn)入度加一/findingreevoid topologicalsort(algraph &g) /對(duì)圖g 進(jìn)行拓?fù)渑判騣nt indegreemax;findingree(g,indegree); /初始化每個(gè)結(jié)點(diǎn)的入度sqstack s;inist_stack(s);

10、/初始化棧for(int j=0;jg.vernum;+j)if(!indegreej)push(s,j); /入度為零的入棧int count=0; /頂點(diǎn)計(jì)數(shù)while(stackempty(s) /棧非空int d;d=pop(s); /出棧coutdnextarc)int k;k=q-adjvex;if(!(-indegreek) push(s,k); /如果頂點(diǎn)入度為零則入棧coutendl;if(countg.vernum) /輸出頂點(diǎn)數(shù)小于所有頂點(diǎn)數(shù)cout有環(huán);/ topologicalsortint vemax,vlmax; /分別記錄各頂點(diǎn)的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間int

11、 topologicalorder(algraph g,sqstack &t) /若無回路，則用棧返回的一個(gè)拓?fù)渑判蛄?，且函?shù)值為，否則為；int indegreemax; findingree(g,indegree); /初始化每個(gè)結(jié)點(diǎn)的入度sqstack s;inist_stack(s); /初始化棧inist_stack(t); for(int j=0;jg.vernum;+j)if(!indegreej)push(s,j); /把所有入度為零的頂點(diǎn)放入棧中int count=0; /記錄頂點(diǎn)數(shù)for(int i=0;inextarc)int k;k=q-adjvex;if(!(-ind

12、egreek)push(s,k); /入度為零的頂點(diǎn)放入棧if(vee+(q-info)vek)vek=vee+(q-info); /計(jì)算各點(diǎn)的最早發(fā)生時(shí)間if(countg.vernum)return 0; /有回路elsereturn 1; /無回路/ topologicalordervoid criticalpath(algraph &g) /輸出圖g的關(guān)鍵路徑sqstack t;if(!topologicalorder(g,t)couterrorendl; /判斷圖是否有環(huán)for(int i=0;inextarc)int k=p-adjvex;int dut=p-info;if(vlk

13、-dutvlj)vlj=vlk-dut; /計(jì)算各頂點(diǎn)的最遲發(fā)生時(shí)間 arcnode *p; /定義頂點(diǎn)指針for(int j1=0;j1nextarc)int k=p-adjvex; /頂點(diǎn)的值int dut=p-info; /頂點(diǎn)的權(quán)值int ee,el; ee=vej1; /頂點(diǎn)的最早發(fā)生時(shí)間el=vlk-dut; /頂點(diǎn)的最遲發(fā)生時(shí)間char tag; /符號(hào)標(biāo)志if(ee=el) tag=*; /頂點(diǎn)的最早發(fā)生時(shí)間等于最遲發(fā)生時(shí)間,輸出*elsetag=#; /頂點(diǎn)的最早發(fā)生時(shí)間不等于最遲發(fā)生時(shí)間，輸出#coutj1 k dut ee el tagendl;/ criticalpat

14、h1. 函數(shù)的調(diào)用關(guān)系圖maincreat_algraphdfstraverse(g)topologicalsortcriticalpathdfsfindingreetopologicalorderfindingreedijkstra算法描述如下：（1） 輸入頂點(diǎn)個(gè)數(shù)n、鄰接矩陣cost和源點(diǎn)序號(hào)i0；（2） 送初值：將i0加入第一組s；令disti=costi0i；(i=1,2,n)；（3） 重復(fù)n-1次做： 在不屬于s的頂點(diǎn)u中，選取具有最小distu值的頂點(diǎn)v； 將v加入s； 對(duì)不屬于s的頂點(diǎn)u做distu=mindistu, distv+costvu;/* distu取distu, d

15、istv+costvu兩個(gè)數(shù)中的最小值*/（4） 輸出各最短路徑的長(zhǎng)度disti及相應(yīng)的最短路徑pre。3調(diào)試報(bào)告在調(diào)試過程中要特別注意函數(shù)調(diào)用時(shí)參數(shù)的傳遞問題，用數(shù)組名作為參數(shù)可進(jìn)行傳值調(diào)用，因而可將函數(shù)中的運(yùn)行結(jié)果傳遞給主調(diào)函數(shù)，得出正確結(jié)果；再一個(gè)要注意的是輸出結(jié)果時(shí)，循環(huán)結(jié)束的條件應(yīng)為：k=i0或k=0時(shí)退出循環(huán)，否則將出現(xiàn)死循環(huán)。另外，上機(jī)前的靜態(tài)檢查不能忽視；程序的調(diào)試過程可暫時(shí)多加一些輸出語句以便及時(shí)查看一下中間運(yùn)行情況并對(duì)程序規(guī)格說明作少量調(diào)整和改動(dòng)。四 程序分析調(diào)試，測(cè)試結(jié)果. 分析調(diào)試 該程序用鄰接表存儲(chǔ)結(jié)構(gòu)，能夠節(jié)省存儲(chǔ)空間。求拓?fù)渑判虻臅r(shí)間復(fù)雜度為o(n*n)，求關(guān)鍵路

16、徑的時(shí)間復(fù)雜度也是o(n*n). 測(cè)試 結(jié)果輸入一個(gè)帶權(quán)有向圖（像這樣輸入（v,w,i）其中v,w為一條邊的兩個(gè)頂點(diǎn)，i為邊的權(quán)值）：（0，1，6），（0，2，4），（0，3，5），（1，4，1），（2，4，1），（3，5，2）,（4，6，9），（4，7，7），（5，7，4），（6，8，2），（7，8，4）。結(jié)果為：五 源程序#include#define max 20typedef struct arcnodeint adjvex; /頂點(diǎn)值struct arcnode *nextarc; /指向下一個(gè)頂點(diǎn)的指針int info; /權(quán)值arcnode;typedef struct vnod

17、eint data; /頂點(diǎn)值arcnode *firstarc; /指向頂點(diǎn)的指針vnode,adjlistmax;typedef structadjlist vertices; int vernum,arcnum; /頂點(diǎn)數(shù)和邊數(shù)int kind;algraph; /圖類型/采用鄰接表存儲(chǔ)結(jié)構(gòu)void creat_algraph(algraph &g)/創(chuàng)建圖coutg.vernum;coutg.arcnum;for(int i=0;ig.vernum;+i)g.verticesi.data=i;g.verticesi.firstarc=null;/頂點(diǎn)初始化cout請(qǐng)輸入各邊，；列入(v

18、 w i),v,w為一條邊的兩個(gè)頂點(diǎn)，從0開始的數(shù)字，i為權(quán)值:endl;arcnode *p;for(int j=0;jvwu; /輸入邊的兩個(gè)頂點(diǎn)和權(quán)值p=new arcnode; /分配一個(gè)頂點(diǎn)空間p-adjvex=w;p-info=u;p-nextarc=g.verticesv.firstarc; g.verticesv.firstarc=p;/定義棧typedef structint *base,*top;int stacksize;sqstack;void inist_stack(sqstack &s)/初始化棧s.base=new int(max);s.top=s.base;s.

19、stacksize=max;int stackempty(sqstack &s)/判斷棧是否為空if(s.base=s.top) /棧頂?shù)扔跅５譺eturn 0;elsereturn 1;void push(sqstack &s,int a)/入棧if(s.top-s.bases.stacksize)*s.top=a;+s.top;int pop(sqstack &s)/出棧if(s.top!=s.base)-s.top;return *s.top;/深度優(yōu)先遍歷圖gbool visitedmax;void dfs(algraph &g,int v);void dfstraverse(algr

20、aph &g)/深度優(yōu)先遍歷圖for(int i1=0;i1g.vernum;+i1)visitedi1=0;for(int j1=0;j1g.vernum;+j1)if(!visitedj1)dfs(g,j1);void dfs(algraph &g,int v)/從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖gvisitedv=1;coutvnextarc)int u;u=q-adjvex;if(!visitedu)dfs(g,u);/拓?fù)渑判騰oid findingree(algraph g,int b20)/計(jì)算圖中每個(gè)頂點(diǎn)的入度for(int j=0;j20;+j)bj=0;for(int i

21、=0;inextarc) /循環(huán)每個(gè)頂點(diǎn)的出邊+bp-adjvex; /計(jì)算每個(gè)頂點(diǎn)的入度void topologicalsort(algraph &g)int indegreemax;findingree(g,indegree);sqstack s;inist_stack(s);for(int j=0;jg.vernum;+j)if(!indegreej)push(s,j);int count=0;coutendl圖的拓?fù)渑判驗(yàn)?;while(stackempty(s) /判斷棧非空就循環(huán)int d;d=pop(s); /出棧coutdnextarc) /循環(huán)所有頂點(diǎn)的出邊int k;k=q

22、-adjvex;if(!(-indegreek)push(s,k); /入度為零就入棧coutendl;if(countg.vernum)cout有環(huán);/求關(guān)鍵路徑int vemax,vlmax;int topologicalorder(algraph g,sqstack &t)int indegreemax;findingree(g,indegree); sqstack s;inist_stack(s);inist_stack(t);for(int j=0;jg.vernum;+j)if(!indegreej)push(s,j); /入度為零就入棧int count=0;for(int i=0;inextarc) /循環(huán)一個(gè)頂點(diǎn)的所有出邊int k;k=q-adjvex;if(!(-indegreek) /判斷入度是否為零push(s,k); /為零入棧if(v