數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告圖的算法實現(xiàn)

1、 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告 課程設(shè)計題目： 圖的算法實現(xiàn) 專業(yè)班級： 信息與計算科學(xué)1002班 姓 名： 學(xué) 號： 設(shè)計室號： 理學(xué)院機房 設(shè)計時間： 2011-12-26 批閱時間： 指導(dǎo)教師： 目錄摘要11、 引言12、 需求分析13、 概要設(shè)計24、 詳細設(shè)計45、 程序設(shè)計106、 運行結(jié)果187、 總結(jié)體會19摘要(題目): 圖的算法實現(xiàn)實驗內(nèi)容 圖的算法實現(xiàn)問題描述：（1）將圖的信息建立文件；（2）從文件讀入圖的信息，建立鄰接矩陣和鄰接表；（3）實現(xiàn)prim、kruskal、dijkstra和拓撲排序算法。關(guān)鍵字: 鄰接矩陣、dijkstra和拓撲排序算法1.引言 本次數(shù)據(jù)結(jié)構(gòu)課

2、程設(shè)計共完成圖的存儲結(jié)構(gòu)的建立、prim、kruskal、dijkstra和拓撲排序算法等問題。通過本次課程設(shè)計，可以鞏固和加深對數(shù)據(jù)結(jié)構(gòu)的理解，通過上機和程序調(diào)試，加深對課本知識的理解和熟練實踐操作。（1） 通過本課程的學(xué)習(xí)，能夠熟練掌握數(shù)據(jù)結(jié)構(gòu)中圖的幾種基本操作；（2） 能針對給定題目，選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，分析并設(shè)計算法，進而給出問題的正確求解過程并編寫代碼實現(xiàn)。使用語言：cprim算法思想：從連通網(wǎng)n=v,e中的某一頂點v0出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(v0,v)，將其頂點加入到生成樹的頂點集合v中。以后每一步從一個頂點在v中，而另一個頂點不在v中的各條邊中選擇權(quán)值最小的邊(u,

3、v),把它的頂點加入到集合v中。如此繼續(xù)下去，直到網(wǎng)中的所有頂點都加入到生成樹頂點集合v中為止。拓撲排序算法思想：1、從有向圖中選取一個沒有前驅(qū)的頂點，并輸出之；2、從有向圖中刪去此頂點以及所有以它為尾的?。恢貜?fù)上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點為止。沒有前驅(qū) - 入度為零，刪除頂點及以它為尾的弧- 弧頭頂點的入度減1。2.需求分析1、 通過鍵盤輸入建立一個新的有向帶權(quán)圖，建立相應(yīng)的文件；2、 對建立的有向帶權(quán)圖進行處理，要求具有如下功能：（1） 用鄰接矩陣和鄰接表的存儲結(jié)構(gòu)輸出該有向帶權(quán)圖，并生成相應(yīng)的輸出結(jié)果；（2） 用prim、kruskal算法實現(xiàn)對圖的最小生成樹的求解

4、，并輸出相應(yīng)的輸出結(jié)果；（3） 用dijkstra算法實現(xiàn)對圖中從某個源點到其余各頂點的最短路徑的求解，并輸出相應(yīng)的輸出結(jié)果；（4）實現(xiàn)該圖的拓撲排序算法。3.概要設(shè)計adt graph 數(shù)據(jù)對象v:v是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集； 數(shù)據(jù)關(guān)系r： r=vr vr=|v,wv且p(v,w),表示從v到w的弧，謂詞p(v,w)定義了弧的意義或信息基本操作：creategraph(&g,v,vr);status creategraph(mgraph &g)/采用鄰接矩陣表示法，構(gòu)造圖g.status creategraph(mgraph &g)/采用鄰接表表示法，構(gòu)造圖gstatus

5、minspantree_prim(mgraph g,vertextype u)/用普里姆算法從第u個頂點出發(fā)構(gòu)造網(wǎng)g的最小生成樹t,輸出t的各條邊status minspantree_ kruskal(mgraph g,vertextype u)/用克魯斯卡爾算法從第u個頂點出發(fā)構(gòu)造網(wǎng)g的最小生成樹t,輸出t的各條邊status shortestpath_dij(mgraph g,int v0,pathmatrix &p,shortpathtable &d)/用 dijkstra算法求有向網(wǎng)g的 v0頂點到其余頂點v的最短路徑pv及帶權(quán)長度dvstatus topsort(algraph g)

6、/若g中無回路，則輸出g的頂點的一個拓撲排序并返回ok,否則返回error存儲結(jié)構(gòu)typedef struct/鄰接矩陣存儲結(jié)構(gòu) int no; int info;vertextype;typedef struct int edgesmaxvmaxv; int n,e; vertextype vexsmaxv;mgraph;typedef struct anode /鄰接表存儲結(jié)構(gòu) int adjvex; struct anode *nextarc; int info;arcnode;typedef struct vnode int data; int count; arcnode *firs

7、tarc;vnode;typedef vnode adjlistmaxv;typedef struct adjlist adjlist; int n,e;algraph;typedef struct node int data; struct node *next;list;4、詳細設(shè)計圖的鄰接矩陣存儲結(jié)構(gòu)算法：status createudn(mgraph &g)/采用鄰接矩陣表示法，構(gòu)造無向網(wǎng)gscanf(&g.vexnum,&g.arcnum,&incinfo); /incinfo為0則各弧不含其他信息for(i=0;ig.vexnum;+i) scanf(&g.vexsi); /構(gòu)造頂

8、點向量for(i=0;ig.vexnum;+i) /初始化鄰接矩陣for(j=0;jg.vexnum;+j) g.arcsij=infinity,null; /adj,infofor(k=0;kg.arcnum;+k) /構(gòu)造鄰接矩陣scanf(&v1,&v2,&w); /輸入一條邊依附的頂點及權(quán)值i=locatevex(g,v1); j=locatevex(g,v2); /確定v1和v2在g中位置g.arcsij.adj=w; /弧的對稱弧return ok;/createudn圖的鄰接表存儲結(jié)構(gòu)算法：void createalgraph(algraph *g) /建立無向圖的鄰接表表示 i

9、nt i，j，k； edgenode *s； scanf( dd ，&g- n，&g- e)； /讀入頂點數(shù)和邊數(shù) for(i=0；i n；i+)/建立頂點表 g- adjlisti.vertex=getchar()； /讀入頂點信息 g- adjlisti.firstedge=null；/邊表置為空表 for(k=0；k e；k+) /建立邊表 scanf( dd ，&i,&j)；讀入邊(vi，vj)的頂點對序號 s=(edgenode *)malloc(sizeof(edgenode)； /生成邊表結(jié)點 s- adjvex=j; /鄰接點序號為j s- next=g- adjlisti.f

10、irstedge； g- adjlisti.firstedge=s； /將新結(jié)點*s插入頂點vi的邊表頭部 s=(edgenode *)malloc(sizeof(edgenode)； s- adjvex=i; /鄰接點序號為i s- next=g- adjlistj.firstedge； g- adjlistkj.firstedge=s； /將新結(jié)點*s插入頂點vj的邊表頭部 /end for createalgraphprim算法實現(xiàn)：public static void prim(int n,float) /prim算法floatlowcost=new floatn+1;intclose

11、st=new intn+1;booleans=new booleann+1;s1=true;for(int i=2;i=n;i+)lowesti=c1i;closesti=1;si=false;for(int i=1;in;i+)float min=float.max_value;int j=1;for(int k=2;k=n;k+)if(lowcostkmin)&(!sk)min=lowcostk;j=k;system.out.println(j+“, ”+closestj);sj=true;for(int k=2;k=n;k+)if(cjk0&kn-1)edgenode x=(edgeno

12、de)h.removemin();e-;int a=u.find(x.u);int b=u.find(x.v);if(a!=b)tk+=x;u.union(a,b);return(k=n-1);dijkstra算法實現(xiàn):public static void dijkstra(int v,floata,floatdist,intprev)/單源最短路徑問題的dijkstra算法int n=dist.length-1;if(vn)return;booleans=new booleann+1;/初始化for(int i=1;i=n;i+)disti=avi;si=false;if(disti=flo

13、at.max_value)previ=0;else previ=v;distv=0;sv=true;for(int i=1;in;i+)float temp=float.max_value;int u=v;for(int j=1;j=n;j+)if(!si)&(distitemp)u=j;temp=distj;su=true;for(int j=1;j=n;j+)if(! s j)&(aujfloat.max_value)float newdist=distu+auj;if(newdistn) for(i=0;in;i+) if(g-adjlisti.count=0&vi=0) pathk=i

14、; k+; vi=1; p=g-adjlisti.firstarc; while(p!=null) j=p-adjvex; g-adjlistj.count-; p=p-nextarc; topsort(g); p=g-adjlisti.firstarc; while(p!=null) j=p-adjvex; g-adjlistj.count+; p=p-nextarc; else for(i=0;ik;i+)printf(%d ,pathi); printf(n); k-; vpathk=0;5、程序設(shè)計#include #include #define maxv 50#define inf

15、 32767typedef int infotype;/鄰接矩陣存儲方法 typedef struct int no; infotype info; vertextype;typedef struct int edgesmaxvmaxv; int n,e; vertextype vexsmaxv; mgraph; /狄克斯特拉算法void ppath(int path,int i,int v) int k; k=pathi; if(k=v) return; ppath(path,k,v); printf(%d,k); void dispath(int dist,int path,int s,i

16、nt n,int v) int i; for(i=0;in;i+) if(i=v) continue; if(si=1) printf(從%d到%d的最短路徑長度為：%dt路徑為：,v,i,disti); printf(%d,v); ppath(path,i,v); printf(%dn,i); else printf(從%d到%d不存在路徑n,v,i); void dijkstra(mgraph g,int v) int distmaxv,pathmaxv; int smaxv; int mindis,i,j,u; for(i=0;ig.n;i+) disti=g.edgesvi; si=0

17、; if(g.edgesviinf) pathi=v; else pathi=-1; sv=1;pathv=0; for(i=0;ig.n;i+) mindis=inf; for(j=0;jg.n;j+) if(sj=0&distjmindis) u=j; mindis=distj; su=1; for(j=0;jg.n;j+) if(sj=0) if(g.edgesujinf&distu+g.edgesujdistj) distj=distu+g.edgesuj; pathj=u; dispath(dist,path,s,g.n,v); /弗洛伊德算法void ppath1(int path

18、maxv,int i,int j) int k; k=pathij; if(k=-1) return; ppath1(path,i,k); printf(%d,k); ppath1(path,k,j); void dispath1(int amaxv,int pathmaxv,int n) int i,j; for(i=0;in;i+) for(j=0;jn;j+) if(i=j) continue; if(aij=inf) if(i!=j) printf(從%d到%d不存在路徑n,i,j); else printf(從%d到%d的最短路徑長度為：%dt路徑為：,i,j,aij); printf(%d,i); ppath1(path,i,j); printf(%dn,j); void floyd(mgraph g) int amaxvmaxv,pathmaxvmaxv; int i,j,k; for(i=0;ig.n;i+) for(j=0;jg.n;j+) aij=g.edgesij; pathij=-1; for(k=0;kg.n;k+) for(i=0;ig.n;i+) for(j=0;jaik+akj) aij=aik+akj; pathij=k; dispath1(a,path,g.n); /主函數(shù)int main() int i,j,n; m