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

1、 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告 課程設(shè)計題目： 圖的算法實現(xiàn) 專業(yè)班級： 信息與計算科學1001班 姓 名： 學 號： 設(shè)計室號： 理學院機房 設(shè)計時間： 2011-12-26 批閱時間： 指導(dǎo)教師： 成 績： 課題：圖的算法實現(xiàn) 任務(wù)要求：（1）將圖的信息建立文件；（2）從文件讀入圖的信息，建立鄰接矩陣和鄰接表；（3）實現(xiàn)prim、kruskal、dijkstra序算法功能、算法、體會描述：系統(tǒng)主要功能是實現(xiàn)圖的算法，主界面選著建立保存圖的信息，可以用普利姆，克魯斯卡爾和狄克斯特拉三種算法分別實現(xiàn)。1建立圖的鄰接矩陣基本思想：輸入頂點和邊數(shù)，輸入頂點信息，算出鄰接矩陣程序模塊：typedef

2、struct char vexsn; int edgesnn; int n,e; /頂點數(shù)和邊數(shù)mgraph;mgraph g;typedef struct char adjvex; int lowcost;minside;/ 若g中存在頂點u,則返回該頂點在圖中位置;否則返回-1。int locatevex(char u)int i; for(i = 0; i g.n; +i)if( u=g.vexsi)return i;else return -1; / 求closedge.lowcost的最小正值int minimum(minside sz) int i=0,j,k,min; while

3、(szi.lowcost=0) i+;min=szi.lowcost; /第一個不為0的值k=i;for(j=i+1;j0)if(minszj.lowcost)min=szj.lowcost;k=j;return k;用outmatrix()函數(shù)輸出鄰接矩陣，getin_1()函數(shù)保存文件和對文件進行載入。程序模塊：void outmatrix()/鄰接矩陣輸出函數(shù) int i,m,z;printf(所建立表的鄰接矩陣為:n); printf(t); for(i=0;ig.n;i+) printf(%ct,g.vexsi); for(m=0;mg.n;m+) printf(n%ct,g.vex

4、sm);for(z=0;zg.n;z+) printf(%dt,g.edgesmz);void getin_1()/ 文件保存函數(shù) int a,b,k,w,z;file *fp; if(fp=fopen(record_1.txt,w)=null) /*打開文件，并判斷打開是否正常*/printf(不能打開文件n); /*沒打開*/ exit(0); printf(請輸入頂點數(shù):n); scanf(%d,&g.n); fprintf(fp,%dn,g.n); printf(請輸入邊數(shù):n); scanf(%d,&g.e); fprintf(fp,%dn,g.e);/初始化矩陣各元素值/讀入邊 p

5、rintf(請輸入頂點信息:n);/頂點的信息會出現(xiàn)在矩陣邊界上。 fflush(stdin);/清空緩沖 for (z=0;zg.n;z+)scanf(%c,&g.vexsz);fprintf(fp,%cn,g.vexsz);for(a=0;ag.n;a+)for(b=0;bg.n;b+)g.edgesab=0;printf(n);printf(請輸入應(yīng)的弧頭a和弧尾b及弧上的權(quán)值w(皆為整數(shù)，,從0開始，格式為:a,b,w):n); for(k=0;kg.e;k+)scanf(%d %d %d,&a,&b,&w);fprintf(fp,%d %d %dn,a,b,w);g.edgesab=

6、w;g.edgesba=w;fclose(fp);void getout_1()/文件載入函數(shù) int i,a,b,w; file *fp; if(fp=fopen(record_1.txt,ab+)=null)printf(不能打開文件n);exit(0); fscanf(fp,%dn,&g.n); fscanf(fp,%dn,&g.e); for(i=0;ig.n;i+)fscanf(fp,%cn,&g.vexsi); for (i=0;ig.n;i+)fscanf(fp,%d %d %dn,&a,&b,&w);g.edgesab=w;g.edgesba=w;2分別用普利姆，克魯斯卡爾和狄

7、克斯特拉算法實現(xiàn)程序模塊：void minispantree_prim(char u) int i,j,k; minside closedge9999; k=locatevex(u); for(j=0;jg.n;+j) /輔助數(shù)組初始化if(j!=k)closedgej.adjvex=u;closedgej.lowcost=g.edgeskj;closedgek.lowcost=0; /初始,u=uprintf(n用prim算法生成的最小生成樹為：n);for(i=1;ig.n;+i) / 選擇其余g.vexnum-1個頂點k=minimum(closedge); / 求出t的下一個結(jié)點：第k

8、頂點 printf(%c-%c)n,closedgek.adjvex,g.vexsk); / 輸出生成樹的邊 closedgek.lowcost=0; / 第k頂點并入u集 for(j=0;jg.n;+j)if(g.edgeskj!=0 & g.edgeskjclosedgej.lowcost) / 新頂點并入u集后重新選擇最小邊closedgej.adjvex=g.vexsk;closedgej.lowcost=g.edgeskj;void ppath(int path,int i,int v) int k; k=pathi; if(k=v) return; ppath(path,k,v);

9、 printf(%d,k);void dispath(int dist,int path,int s,int 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(int v) int distn,pathn; int sn; int mindis,i,j,u;for(i=0;i

10、g.n;i+) for(j=0;jg.n;j+)if(g.edgesij=0)g.edgesij=9999; for(i=0;ig.n;i+) disti=g.edgesvi; si=0;if(g.edgesvi9999) pathi=v; else pathi=-1; sv=1; pathv=0; for(i=0;ig.n;i+) mindis=9999; 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.edgesuj9999&distu+g.edgesuj0)

11、t=frontt;return t;void kruskal(edgetype edges,int n)int front100;int i,vf1,vf2;printf(用kruskal算法生成的最小生成樹為：n);for(i=0;in;i+)fronti=0;for(i=0;in-1;i+)vf1=search(front,edgesi.w1);vf2=search(front,edgesi.w2);if(vf1!=vf2)frontvf2=vf1;printf(%c-%c)n,edgesi.w1,edgesi.w2);3主函數(shù)void main() int a,i;printf(tt*圖

12、的實現(xiàn)算法*n);printf(tt*nn);printf(ttt1:建立圖的鄰接矩陣nn);printf(ttt2:用prim算法生成的最小生成樹為：nn);printf(ttt3:用dijkstra生成的最短路徑nn);printf(ttt4:用kruskal算法生成的最小生成樹為：nn);printf(ttt5:返回nn);printf(tt*n);printf(tt*n);printf(ntt輸入一個有效的數(shù)字,選擇你要做的操作:n); system(color a);/*改變界面顏色的，對程序沒什么影響*/ scanf(%d,&a);switch(a)case 1:system(cl

13、s); printf(輸入數(shù)據(jù)建立無向圖的鄰接矩陣);getin_1();printf(數(shù)據(jù)保存成功！n);/*flag_1=1;undigraph();*/main();break; case 2:getout_1();outmatrix();minispantree_prim(g.vexs0);/用prim算法求最小生成樹main();break;case 3:getout_1();outmatrix();printf(n采用dijkstra算法得到的最短路徑為：n); for(i=0;ig.n;i+)dijkstra(i);printf(n);main();break; case 5:m

14、ain();case 4:getout_1();outmatrix();printf(n); edgetype edgex1000; int p,q,c=0;for(p=0;pg.n;p+)for(q=p+1;q=g.n;q+)edgexc+.cost=g.edgespq;edgex-c.w1=g.vexsp;edgexc+.w2=g.vexsq;kruskal(edgex,g.e);main();break;功能調(diào)試主界面建立圖的信息用普利姆算法生成最小生成樹用狄克斯特拉算法生成最短路徑用克魯斯卡爾算法生成最小生成樹返回程序源代碼#include#include#define n 9999t

15、ypedef int elemtype;typedef structelemtype w1;elemtype w2;int cost;edgetype;typedef struct char vexsn; int edgesnn; int n,e; /頂點數(shù)和邊數(shù)mgraph;mgraph g;typedef struct char adjvex; int lowcost;minside;/ 若g中存在頂點u,則返回該頂點在圖中位置;否則返回-1。int locatevex(char u)int i; for(i = 0; i g.n; +i)if( u=g.vexsi)return i;el

16、se return -1; / 求closedge.lowcost的最小正值int minimum(minside sz) int i=0,j,k,min; while(szi.lowcost=0) i+;min=szi.lowcost; /第一個不為0的值k=i;for(j=i+1;j0)if(minszj.lowcost)min=szj.lowcost;k=j;return k;/用prim算法從第u個頂點出發(fā)構(gòu)造網(wǎng)g的最小生成樹t,輸出t的各條邊void minispantree_prim(char u) int i,j,k; minside closedge9999; k=locate

17、vex(u); for(j=0;jg.n;+j) /輔助數(shù)組初始化if(j!=k)closedgej.adjvex=u;closedgej.lowcost=g.edgeskj;closedgek.lowcost=0; /初始,u=uprintf(n用prim算法生成的最小生成樹為：n);for(i=1;ig.n;+i) / 選擇其余g.vexnum-1個頂點k=minimum(closedge); / 求出t的下一個結(jié)點：第k頂點 printf(%c-%c)n,closedgek.adjvex,g.vexsk); / 輸出生成樹的邊 closedgek.lowcost=0; / 第k頂點并入u

18、集 for(j=0;jg.n;+j)if(g.edgeskj!=0 & g.edgeskjclosedgej.lowcost) / 新頂點并入u集后重新選擇最小邊closedgej.adjvex=g.vexsk;closedgej.lowcost=g.edgeskj;void outmatrix()/鄰接矩陣輸出函數(shù) int i,m,z;printf(所建立表的鄰接矩陣為:n); printf(t); for(i=0;ig.n;i+) printf(%ct,g.vexsi); for(m=0;mg.n;m+) printf(n%ct,g.vexsm);for(z=0;zg.n;z+) prin

19、tf(%dt,g.edgesmz);void getin_1()/ 文件保存函數(shù) int a,b,k,w,z;file *fp; if(fp=fopen(record_1.txt,w)=null) /*打開文件，并判斷打開是否正常*/printf(不能打開文件n); /*沒打開*/ exit(0); printf(請輸入頂點數(shù):n); scanf(%d,&g.n); fprintf(fp,%dn,g.n); printf(請輸入邊數(shù):n); scanf(%d,&g.e); fprintf(fp,%dn,g.e);/初始化矩陣各元素值/讀入邊 printf(請輸入頂點信息:n);/頂點的信息會出

20、現(xiàn)在矩陣邊界上。 fflush(stdin);/清空緩沖 for (z=0;zg.n;z+)scanf(%c,&g.vexsz);fprintf(fp,%cn,g.vexsz);for(a=0;ag.n;a+)for(b=0;bg.n;b+)g.edgesab=0;printf(n);printf(請輸入應(yīng)的弧頭a和弧尾b及弧上的權(quán)值w(皆為整數(shù)，,從0開始，格式為:a,b,w):n); for(k=0;kg.e;k+)scanf(%d %d %d,&a,&b,&w);fprintf(fp,%d %d %dn,a,b,w);g.edgesab=w;g.edgesba=w;fclose(fp);

21、void getout_1()/文件載入函數(shù) int i,a,b,w; file *fp; if(fp=fopen(record_1.txt,ab+)=null)printf(不能打開文件n);exit(0); fscanf(fp,%dn,&g.n); fscanf(fp,%dn,&g.e); for(i=0;ig.n;i+)fscanf(fp,%cn,&g.vexsi); for (i=0;ig.n;i+)fscanf(fp,%d %d %dn,&a,&b,&w);g.edgesab=w;g.edgesba=w;/用狄克斯特拉算法求最短路徑void ppath(int path,int i,

22、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,int 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(int

23、 v) int distn,pathn; int sn; int mindis,i,j,u;for(i=0;ig.n;i+) for(j=0;jg.n;j+)if(g.edgesij=0)g.edgesij=9999; for(i=0;ig.n;i+) disti=g.edgesvi; si=0;if(g.edgesvi9999) pathi=v; else pathi=-1; sv=1; pathv=0; for(i=0;ig.n;i+) mindis=9999; for(j=0;jg.n;j+) if(sj=0&distjmindis)u=j; mindis=distj;su=1; for

24、(j=0;jg.n;j+)if(sj=0)if(g.edgesuj9999&distu+g.edgesuj0)t=frontt;return t;void kruskal(edgetype edges,int n)int front100;int i,vf1,vf2;printf(用kruskal算法生成的最小生成樹為：n);for(i=0;in;i+)fronti=0;for(i=0;in-1;i+)vf1=search(front,edgesi.w1);vf2=search(front,edgesi.w2);if(vf1!=vf2)frontvf2=vf1;printf(%c-%c)n,edgesi.w1,edgesi.w2);void main() int a,i;printf(tt*圖的實