数据结构与算法课程设计报告-图的算法实现.doc

《数据结构与算法课程设计报告-图的算法实现.doc》由会员分享，可在线阅读，更多相关《数据结构与算法课程设计报告-图的算法实现.doc（23页珍藏版）》请在三一文库上搜索。

1、 数据结构与算法课程设计报告 课程设计题目： 图的算法实现 专业班级： 信息与计算科学1001班 姓 名： 学 号： 设计室号： 理学院机房 设计时间： 2011-12-26 批阅时间： 指导教师： 成 绩： 课题：图的算法实现 任务要求：（1）将图的信息建立文件；（2）从文件读入图的信息，建立邻接矩阵和邻接表；（3）实现Prim、Kruskal、Dijkstra序算法功能、算法、体会描述：系统主要功能是实现图的算法，主界面选着建立保存图的信息，可以用普利姆，克鲁斯卡尔和狄克斯特拉三种算法分别实现。1建立图的邻接矩阵基本思想：输入顶点和边数，输入顶点信息，算出邻接矩阵程序模块：typedef

2、struct char vexsN; int edgesNN; int n,e; /顶点数和边数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()函数输出邻接矩阵，getin_1()函数保存文件和对文件进行载入。程序模块：void outmatrix()/邻接矩阵输出函数 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()/ 文件保存函数 int a,b,k,w,z;FILE *fp; if(fp=fopen(record_1.txt,w)=NULL) /*打开文件，并判断打开是否正常*/printf(不能打开文件n); /*没打开*/ exit(0); printf(请输入顶点数:n); scanf(%d,&g.n); fprintf(fp,%dn,g.n); printf(请输入边数:n); scanf(%d,&g.e); fprintf(fp,%dn,g.e);/初始化矩阵各元素值/读入边 p

5、rintf(请输入顶点信息: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(请输入应的弧头a和弧尾b及弧上的权值w(皆为整数，,从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()/文件载入函数 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、克斯特拉算法实现程序模块：void MiniSpanTree_PRIM(char u) int i,j,k; minside closedge9999; k=LocateVex(u); for(j=0;jg.n;+j) /辅助数组初始化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的下一个结点：第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主函数void main() int a,i;printf(tt*图

12、的实现算法*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输入一个有效的数字,选择你要做的操作:n); system(color A);/*改变界面颜色的，对程序没什么影响*/ scanf(%d,&a);switch(a)case 1:system(cl

13、s); printf(输入数据建立无向图的邻接矩阵);getin_1();printf(数据保存成功！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;功能调试主界面建立图的信息用普利姆算法生成最小生成树用狄克斯特拉算法生成最短路径用克鲁斯卡尔算法生成最小生成树返回程序源代码#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; /顶点数和边数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个顶点出发构造网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) /辅助数组初始化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的下一个结点：第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()/邻接矩阵输出函数 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()/ 文件保存函数 int a,b,k,w,z;FILE *fp; if(fp=fopen(record_1.txt,w)=NULL) /*打开文件，并判断打开是否正常*/printf(不能打开文件n); /*没打开*/ exit(0); printf(请输入顶点数:n); scanf(%d,&g.n); fprintf(fp,%dn,g.n); printf(请输入边数:n); scanf(%d,&g.e); fprintf(fp,%dn,g.e);/初始化矩阵各元素值/读入边 printf(请输入顶点信息:n);/顶点的信息会出

20、现在矩阵边界上。 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(请输入应的弧头a和弧尾b及弧上的权值w(皆为整数，,从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()/文件载入函数 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,e

25、dgesi.w1,edgesi.w2);void main() int a,i;printf(tt*图的实现算法*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输入一个有效的数字,选择你要做的操作:n); system(color A);/*改变界面颜色

26、的，对程序没什么影响*/ scanf(%d,&a);switch(a)case 1:system(cls); printf(输入数据建立无向图的邻接矩阵);getin_1();printf(数据保存成功！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:main();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;