數據結構與算法課程設計報告---圖的算法實現

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：22 大小：188.00KB 人氣指數：12 舉報 版權申訴

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

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數據結構與算法　　課程設計報告　　課程設計題目：圖的算法實現 　　專業(yè)班級：信息與計算科學1002班

2、 　　目錄　　摘要…………………………………………………1　　引言……………………………………………1　　需求分析………………………………………1　　概要設計……………………

3、…………………2　　詳細設計………………………………………4　　程序設計………………………………………10　　運行結果………………………………………18　　總結體會………………………………………19　　摘要(題目): 圖的算法實現

4、　　實驗內容　　圖的算法實現　　問題描述：　?。?）將圖的信息建立文件；　　（2）從文件讀入圖的信息，建立鄰接矩陣和

5、鄰接表；　?。?）實現Prim、Kruskal、Dijkstra和拓撲排序算法。　　關鍵字: 鄰接矩陣、Dijkstra和拓撲排序算法　　1.引言 　　本次數據結構課程設計共完成圖的存儲結構的建立、Prim、Kruskal、Dijks

6、tra和拓撲排序算法等問題。通過本次課程設計，可以鞏固和加深對數據結構的理解，通過上機和程序調試，加深對課本知識的理解和熟練實踐操作。　　通過本課程的學習，能夠熟練掌握數據結構中圖的幾種基本操作；　　能針對給定題目，選擇相應的數據結構，分析并設計算法，進而給出問題的正確求解過程并編寫代碼實現。

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

8、　　拓撲排序算法思想：　　1、從有向圖中選取一個沒有前驅的頂點，并輸出之； 2、從有向圖中刪去此頂點以及所有以它為尾的??；重復上述兩步，直至圖空，或者圖不空但找不到無前驅的頂點為止。沒有前驅 -- 入度為零，刪除頂點及以它為尾的弧-- 弧頭頂點的入度減1。<

9、;p>　　2.需求分析　　通過鍵盤輸入建立一個新的有向帶權圖，建立相應的文件；　　對建立的有向帶權圖進行處理，要求具有如下功能：　　用鄰接矩陣和鄰接表的存儲結構輸出該有向帶權圖，并生成相應的輸出結果；　　用Prim、Kruska

10、l算法實現對圖的最小生成樹的求解，并輸出相應的輸出結果；　　用Dijkstra算法實現對圖中從某個源點到其余各頂點的最短路徑的求解，并輸出相應的輸出結果；　?。?）實現該圖的拓撲排序算法。　　3.概要設計　　ADT Graph{<

11、;/p>　　數據對象V:V是具有相同特性的數據元素的集合，稱為頂點集；　　數據關系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.&l

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

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

15、athTable &D)　　//用 Dijkstra算法求有向網G的 v0頂點到其余頂點v的最短路徑P[v]及帶權長度D[v]　　Status TopSort(ALGraph G)　　//若G中無回路，則輸出G的頂點的一個拓撲排序并返回OK,否則返回ERROR&l

16、t;b>　　存儲結構　　typedef struct//鄰接矩陣存儲結構 　　{　　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 //鄰接表存儲結構 　　{ 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、詳細設計　　圖的鄰接矩陣存儲結構算法：　　Status CreateUDN(MGraph &G){　　//采用鄰接矩陣表示法，構造無向網G　　Scanf(&G.vexnum,&G.arcnum,&

24、amp;IncInfo); //IncInfo為0則各弧不含其他信息　　for(i=0;i<G.vexnum;++i) scanf(&G.vexs[i]); //構造頂點向量　　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){ //構造鄰接矩陣　　scanf(&v1,&v2,&w); //輸入一條邊依附的頂點及權值　　i=Loca

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

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

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

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

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

31、60; scanf( "％d％d "，&i,&j)；讀入邊(vi，vj)的頂點對序號 s=(EdgeNode *)malloc(sizeof　　Prim算法實現：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算法實現：　　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算法實現:　　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>　　}}　　}　　}　　圖的拓撲排序算法：　　void TopSort(ALGraph *G) &l

49、t;p>　　{//若G中無回路，則返回G的一個拓撲排序，且函數值為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、程序設計　　#include <stdio.h></p&g

56、t;　　#include <stdlib.h>　　#define MAXV 50　　#define INF 32767　　typedef int InfoType;　　//鄰接矩陣存儲方法 　　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>　　} //主函數　　int main()　　{ int i,j,n;　　MGraph g;　　printf("請輸入帶權有向圖的頂點個數：");//6

86、　　while(scanf("%d",&n)!=EOF) 　　{　　printf("請輸入帶權有向圖的鄰接矩陣：\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請輸入帶權無向圖的頂點個數：");　　}　　return 0;　　}</

92、p>　　6、程序運行結果：　　總結體會　　通過本次課程設計，對圖的概念有了一個新的認識，在學習離散數學的時候，總覺得圖是很抽象的東西，但是在學習了《數據結構》后，我慢慢體會到了其中的奧妙，圖能夠在計算機中存在，首先要知道它有哪些具體化、數字化的信息，比

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

溫馨提示

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

數據結構與算法課程設計報告---圖的算法實現

文檔簡介

溫馨提示

最新文檔

評論

數據結構與算法課程設計報告---圖的算法實現

文檔簡介

溫馨提示

最新文檔

評論

免費下載