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

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁數(shù)：22 大?。?88.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁，還剩21頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)與算法　　課程設(shè)計(jì)報(bào)告　　課程設(shè)計(jì)題目：圖的算法實(shí)現(xiàn) 　　專業(yè)班級(jí)：信息與計(jì)算科學(xué)1002班

2、 　　目錄　　摘要…………………………………………………1　　引言……………………………………………1　　需求分析………………………………………1　　概要設(shè)計(jì)……………………

3、…………………2　　詳細(xì)設(shè)計(jì)………………………………………4　　程序設(shè)計(jì)………………………………………10　　運(yùn)行結(jié)果………………………………………18　　總結(jié)體會(huì)………………………………………19　　摘要(題目): 圖的算法實(shí)現(xiàn)

4、　　實(shí)驗(yàn)內(nèi)容　　圖的算法實(shí)現(xiàn)　　問題描述：　　（1）將圖的信息建立文件；　　（2）從文件讀入圖的信息，建立鄰接矩陣和

5、鄰接表；　?。?）實(shí)現(xiàn)Prim、Kruskal、Dijkstra和拓?fù)渑判蛩惴ā?lt;/p>　　關(guān)鍵字: 鄰接矩陣、Dijkstra和拓?fù)渑判蛩惴?lt;/p>　　1.引言 　　本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)共完成圖的存儲(chǔ)結(jié)構(gòu)的建立、Prim、Kruskal、Dijks

6、tra和拓?fù)渑判蛩惴ǖ葐栴}。通過本次課程設(shè)計(jì)，可以鞏固和加深對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，通過上機(jī)和程序調(diào)試，加深對(duì)課本知識(shí)的理解和熟練實(shí)踐操作。　　通過本課程的學(xué)習(xí)，能夠熟練掌握數(shù)據(jù)結(jié)構(gòu)中圖的幾種基本操作；　　能針對(duì)給定題目，選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，分析并設(shè)計(jì)算法，進(jìn)而給出問題的正確求解過程并編寫代碼實(shí)現(xiàn)。

7、　使用語言：C　　Prim算法思想：從連通網(wǎng)N={V,E}中的某一頂點(diǎn)v0出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(v0,v)，將其頂點(diǎn)加入到生成樹的頂點(diǎn)集合V中。以后每一步從一個(gè)頂點(diǎn)在V中，而另一個(gè)頂點(diǎn)不在V中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點(diǎn)加入到集合V中。如此繼續(xù)下去，直到網(wǎng)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合V中為止。

8、　　拓?fù)渑判蛩惴ㄋ枷耄?lt;/b>　　1、從有向圖中選取一個(gè)沒有前驅(qū)的頂點(diǎn)，并輸出之； 2、從有向圖中刪去此頂點(diǎn)以及所有以它為尾的弧；重復(fù)上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點(diǎn)為止。沒有前驅(qū) -- 入度為零，刪除頂點(diǎn)及以它為尾的弧-- 弧頭頂點(diǎn)的入度減1。<

9、;p>　　2.需求分析　　通過鍵盤輸入建立一個(gè)新的有向帶權(quán)圖，建立相應(yīng)的文件；　　對(duì)建立的有向帶權(quán)圖進(jìn)行處理，要求具有如下功能：　　用鄰接矩陣和鄰接表的存儲(chǔ)結(jié)構(gòu)輸出該有向帶權(quán)圖，并生成相應(yīng)的輸出結(jié)果；　　用Prim、Kruska

10、l算法實(shí)現(xiàn)對(duì)圖的最小生成樹的求解，并輸出相應(yīng)的輸出結(jié)果；　　用Dijkstra算法實(shí)現(xiàn)對(duì)圖中從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑的求解，并輸出相應(yīng)的輸出結(jié)果；　?。?）實(shí)現(xiàn)該圖的拓?fù)渑判蛩惴ā?lt;/p>　　3.概要設(shè)計(jì)　　ADT Graph{<

11、;/p>　　數(shù)據(jù)對(duì)象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集；　　數(shù)據(jù)關(guān)系R：　　R={VR}　　VR={<v,w>|v,w∈V且P(v,w),<v,w>表示從v到w的弧，謂詞P

12、(v,w)定義了弧<v,w>的意義或信息}　　基本操作：　　CreateGraph(&G,V,VR);　　Status CreateGraph(MGraph &G)　　//采用鄰接矩陣表示法，構(gòu)造圖G.&l

13、t;/p>　　Status CreateGraph(MGraph &G)　　//采用鄰接表表示法，構(gòu)造圖G　　Status MinSpanTree_Prim(MGraph G,VertexType u)　　//用普里姆算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹T,輸出T的各條邊&

14、lt;/p>　　Status MinSpanTree_ Kruskal(MGraph G,VertexType u)　　//用克魯斯卡爾算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹T,輸出T的各條邊　　Status ShortestPath_DIJ(MGraph G,int v0,PathMatrix &p,ShortP

15、athTable &D)　　//用 Dijkstra算法求有向網(wǎng)G的 v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑P[v]及帶權(quán)長度D[v]　　Status TopSort(ALGraph G)　　//若G中無回路，則輸出G的頂點(diǎn)的一個(gè)拓?fù)渑判虿⒎祷豋K,否則返回ERROR&l

16、t;b>　　存儲(chǔ)結(jié)構(gòu)　　typedef struct//鄰接矩陣存儲(chǔ)結(jié)構(gòu) 　　{　　int no;　　int info;</p

17、>　　}VertexType;　　typedef struct　　{　　int edges[MAXV][MAXV];　　int n,e;<

18、p>　　VertexType vexs[MAXV];　　}MGraph;　　typedef struct ANode //鄰接表存儲(chǔ)結(jié)構(gòu) 　　{ int adjvex;　　struct ANode *nextarc

19、;　　int info;　　}ArcNode;　　typedef struct Vnode　　{

20、　int data;　　int count; 　　ArcNode *firstarc;　　}VNode;　　typedef VNode AdjList[MAXV];　　ty

21、pedef struct 　　{　　AdjList adjlist;　　int n,e;　　}ALGraph;

22、typedef struct node　　{　　int data;　　struct node *next;　　}List;<p&

23、gt;　　4、詳細(xì)設(shè)計(jì)　　圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)算法：　　Status CreateUDN(MGraph &G){　　//采用鄰接矩陣表示法，構(gòu)造無向網(wǎng)G　　Scanf(&G.vexnum,&G.arcnum,&

24、amp;IncInfo); //IncInfo為0則各弧不含其他信息　　for(i=0;i<G.vexnum;++i) scanf(&G.vexs[i]); //構(gòu)造頂點(diǎn)向量　　for(i=0;i<G.vexnum;++i) //初始化鄰接矩陣　　for(j=0;j<G.v

25、exnum;++j) G.arcs[i][j]={INFINITY,NULL}; //{adj,info}　　for(k=0;k<G.arcnum;++k){ //構(gòu)造鄰接矩陣　　scanf(&v1,&v2,&w); //輸入一條邊依附的頂點(diǎn)及權(quán)值　　i=Loca

26、teVex(G,v1); j=LocateVex(G,v2); //確定v1和v2在G中位置　　G.arcs[i][j].adj=w; //弧<v1,v2>的對(duì)稱弧<v2,v1>　　}　　Return Ok;<p

27、>　　}//CreateUDN　　圖的鄰接表存儲(chǔ)結(jié)構(gòu)算法：　　void CreateALGraPh(ALGraph *G) { //建立無向圖的鄰接表表示 int

28、0; i，j，k； EdgeNode *s； scanf( "％d％d "，&G-> n，&G-> e)； //讀入頂點(diǎn)數(shù)和邊數(shù) &#

29、160; for(i=0；i <G-> n；i++){//建立頂點(diǎn)表 G-> adjlist[i].vertex=getchar()； //讀入頂點(diǎn)信息 G->

30、 adjlist[i].firstedge=NULL；//邊表置為空表 } for(k=0；k <G-> e；k++){ //建立邊表

31、60; scanf( "％d％d "，&i,&j)；讀入邊(vi，vj)的頂點(diǎn)對(duì)序號(hào) s=(EdgeNode *)malloc(sizeof　　Prim算法實(shí)現(xiàn)：Public static void pri

32、m(int n,float[][]) //prim算法　　{float[]lowcost=new float[n+1];　　Int[]closest=new int[n+1];　　Boolean[]s=new boolean[n+1];　　S[1]=true;</

33、p>　　for(int i=2;i<=n;i++){　　Lowest[i]=c[1][i];　　Closest[i]=1;　　S[i]=false;　　}

34、for(int i=1;i<n;i++){　　float min=Float.MAX_VALUE;　　int j=1;　　for(int k=2;k<=n;k++)　　if((lowcost[k]<min)&

35、&(!s[k])){　　min=lowcost[k];　　j=k;　　}　　System.out.println(j+“, ”+closest[j]);<p&

36、gt;　　S[j]=true;　　for(int k=2;k<=n;k++)　　if((c[j][k]<lowcost[k])&&(!s[k])){　　lowcost[k]=c[j][k];　　closest[k]=j;

37、　　}　　}　　}　　Kruskal算法實(shí)現(xiàn)：　　Public static Boolean Kruskal(int n,int e,Edg

38、eNode[] E,EdgeNode[] t)　　{　　MinHeap H=new MinHeap(1);　　H.initialize(E,e);　　FastUnionFind U=new FastUnionFind(n);</

39、p>　　Int k=0;　　While(e>0&&k<n-1){　　EdgeNode x=(EdgeNode)H.removeMin();　　e--;<

40、p>　　int a=U.find(x.u);　　int b=U.find(x.v);　　if(a!=b){　　t[k++]=x;　　U.union(a,b);}<

41、;p>　　}　　Return(k==n-1);　　}　　Dijkstra算法實(shí)現(xiàn):　　Public static void Dijkstra(int v,float[][]a,float[]

42、dist,int[]prev)　　{//單源最短路徑問題的Dijkstra算法　　Int n=dist.length-1;　　If(v<1||v>n)return;　　Boolean[]s=new Boolean[n+1];<p&

43、gt;　　//初始化　　for(int i=1;i<=n;i++){　　dist[i]=a[v][i];　　s[i]=false;　　if(dist[i]==Float.MAX_VALUE)prev[i]=0;

44、;　　else prev[i]=v;　　}　　Dist[v]=0;s[v]=true;　　for(int i=1;i<n;i++){　　float temp=Float.MAX_VALUE;</p&g

45、t;　　int u=v;　　for(int j=1;j<=n;j++)　　if((!s[i])&&(dist[i]<temp)){　　u=j;

46、temp=dist[j];　　}　　s[u]=true;　　for(int j=1;j<=n;j++)　　if((! s [j])&&(a[u][j]<Float.MAX_VALUE)){

47、;　　float newdist=dist[u]+a[u][j];　　if(newdist<dist[j]){　　//dist[j]減少　　dist[j]=newdist;　　prev[j]=u;<

48、;b>　　}}　　}　　}　　圖的拓?fù)渑判蛩惴ǎ?lt;/b>　　void TopSort(ALGraph *G) &l

49、t;p>　　{//若G中無回路，則返回G的一個(gè)拓?fù)渑判?，且函?shù)值為OK，否則為ERROR　　int i,j;　　ArcNode *p;　　if(k!=G->n)　　{for(i=0;i<G->n;i++)<

50、;/p>　　{if(G->adjlist[i].count==0&&v[i]==0)　　{path[k]=i;　　k++;　　v[i]=1;

51、p=G->adjlist[i].firstarc;　　while(p!=NULL)　　{ j=p->adjvex;　　G->adjlist[j].count--;　　p=p->nextarc;<b&g

52、t;　　}　　TopSort(G);　　p=G->adjlist[i].firstarc;　　while(p!=NULL)　　{ j=p->adjvex;　　G->adjlist[j].cou

53、nt++;　　p=p->nextarc;　　}　　}　　}　　}<

54、/p>　　else 　　{ for(i=0;i<k;i++)printf("%d ",path[i]); 　　printf("\n");　　}</p&g

55、t;　　k--;　　v[path[k]]=0;　　}　　5、程序設(shè)計(jì)　　#include <stdio.h></p&g

56、t;　　#include <stdlib.h>　　#define MAXV 50　　#define INF 32767　　typedef int InfoType;　　//鄰接矩陣存儲(chǔ)方法 　　t

57、ypedef struct　　{　　int no;　　InfoType info;　　} VertexType;　　typedef struct</

58、p>　　{　　int edges[MAXV][MAXV];　　int n,e;　　VertexType vexs[MAXV];　　} MGraph;

59、;　　//狄克斯特拉算法　　void Ppath(int path[],int i,int v)　　{　　int k;　　k=path[

60、i];　　if(k==v) return;　　Ppath(path,k,v);　　printf("%d,",k);　　} 　　void Dispath(int dist

61、[],int path[],int s[],int n,int v)　　{　　int i;　　for(i=0;i<n;i++)　　{

62、　　if(i==v) continue;　　if(s[i]==1)　　{　　printf("從%d到%d的最短路徑長度為：%d\t路徑為：",v,i,dist[i]);　　printf(&qu

63、ot;%d,",v);　　Ppath(path,i,v);　　printf("%d\n",i);　　} 　　else printf("從%d到%d不存在路徑\n",v,i);&l

64、t;/p>　　} 　　} 　　void Dijkstra(MGraph g,int v)　　{　　int dist[MAXV

65、],path[MAXV];　　int s[MAXV];　　int mindis,i,j,u;　　for(i=0;i<g.n;i++)　　{　　dist[i]=g.edges[v][i];

66、　　s[i]=0;　　if(g.edges[v][i]<INF) path[i]=v;　　else path[i]=-1;　　} 　　s[v]=1;

67、path[v]=0;　　for(i=0;i<g.n;i++)　　{　　mindis=INF;　　for(j=0;j<g.n;j++)　　{&l

68、t;/p>　　if(s[j]==0&&dist[j]<mindis)　　{　　u=j;　　mindis=dist[j];　　}

69、 　　} 　　s[u]=1;　　for(j=0;j<g.n;j++)　　{　　i

70、f(s[j]==0)　　{　　if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j])　　{　　dist[j]=dist

71、[u]+g.edges[u][j];　　path[j]=u;　　} 　　} 　　} <b&g

72、t;　　} 　　Dispath(dist,path,s,g.n,v); 　　} 　　//弗洛伊德算法　　void Ppath1(int path[][MAXV],int

73、 i,int j)　　{　　int k;　　k=path[i][j];　　if(k==-1) return;　　Ppath1(path,i,k);<

74、/p>　　printf("%d,",k);　　Ppath1(path,k,j);　　} 　　void Dispath1(int A[][MAXV],int path[][MAXV],int n)<

75、;p>　　{　　int i,j;　　for(i=0;i<n;i++)　　{　　for(j=0;j<n;j++)<

76、;p>　　{　　if(i==j) continue;　　if(A[i][j]==INF)　　{　　if(i!=j) printf("從%d到%d不存在路徑\n",i,j)

77、;　　} 　　else　　{　　printf("從%d到%d的最短路徑長度為：%d\t路徑為：",i,j,A[i][j]);<

78、/p>　　printf("%d,",i);　　Ppath1(path,i,j);　　printf("%d\n",j);　　} 　　} &

79、lt;/b>　　} 　　} 　　void Floyd(MGraph g)　　{　　int A[MAXV]

80、[MAXV],path[MAXV][MAXV];　　int i,j,k;　　for(i=0;i<g.n;i++)　　{　　for(j=0;j<g.n;j++)

81、{　　A[i][j]=g.edges[i][j];　　path[i][j]=-1; 　　} 　　} 　　for(k=0;k<

82、;g.n;k++)　　{　　for(i=0;i<g.n;i++)　　{　　for(j=0;j<g.n;j++)　　{<

83、/b>　　if(A[i][j]>A[i][k]+A[k][j])　　{　　A[i][j]=A[i][k]+A[k][j];　　path[i][j]=k;　　}

84、 　　}　　}　　} 　　Dispath1(A,path,g.n); &

85、lt;b>　　} //主函數(shù)　　int main()　　{ int i,j,n;　　MGraph g;　　printf("請(qǐng)輸入帶權(quán)有向圖的頂點(diǎn)個(gè)數(shù)：");//6

86、　　while(scanf("%d",&n)!=EOF) 　　{　　printf("請(qǐng)輸入帶權(quán)有向圖的鄰接矩陣：\n"); 　　/*<p&

87、gt;　　0 5 32767 7 32767 32767　　32767 0 4 32767 32767 32767　　8 32767 0 32767 32767 9　　32767 32767 5 0 32767 6　　32767 32767 32767 5 0 32767

88、　　3 32767 32767 32767 1 0　　*/ 　　for(i=0;i<n;i++)　　{　　for(j=0;j<n;j++)

89、　　{　　scanf("%d",&g.edges[i][j]);　　}　　}<b&

90、gt;　　g.n=n;　　printf("采用狄克斯特拉算法得到的最短路徑為：\n");　　for(i=0;i<n;i++) Dijkstra(g,i);printf("\n"); 　　printf("采用弗洛伊德算法得到的最短路徑為：\

91、n");Floyd(g);　　printf("\n請(qǐng)輸入帶權(quán)無向圖的頂點(diǎn)個(gè)數(shù)：");　　}　　return 0;　　}</

92、p>　　6、程序運(yùn)行結(jié)果：　　總結(jié)體會(huì)　　通過本次課程設(shè)計(jì)，對(duì)圖的概念有了一個(gè)新的認(rèn)識(shí)，在學(xué)習(xí)離散數(shù)學(xué)的時(shí)候，總覺得圖是很抽象的東西，但是在學(xué)習(xí)了《數(shù)據(jù)結(jié)構(gòu)》后，我慢慢體會(huì)到了其中的奧妙，圖能夠在計(jì)算機(jī)中存在，首先要知道它有哪些具體化、數(shù)字化的信息，比

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評(píng)論

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

文檔簡介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載