图的算法实现

《图的算法实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、本思想：输入顶点和边数，输入顶点信息，算出邻接矩阵程序模块：typedefstruct{charvexs[N];intedges[N][N];intn,e;//顶点数和边数}MGraph;MGraphg;typedefstruct{charadjvex;intlowcost;}minside;//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。intLocateVex(charu){inti;for(i=0;i

3、/求closedge.lowcost的最小正值intminimum(minsideSZ[]){inti=0,j,k,min;while(SZ[i].lowcost==0)i++;min=SZ[i].lowcost;//第一个不为0的值k=i;for(j=i+1;j0)if(min>SZ[j].lowcost){min=SZ[j].lowcost;k=j;}returnk;}用outmatrix()函数输出邻接矩阵，getin_1()函数保存文件和对文件进行载入。

4、程序模块：voidoutmatrix()//邻接矩阵输出函数{inti,m,z;printf("所建立表的邻接矩阵为:");printf("t");for(i=0;i

5、f((fp=fopen("record_1.txt","w"))==NULL)/*打开文件，并判断打开是否正常*/{printf("不能打开文件");/*没打开*/exit(0);}printf("请输入顶点数:");scanf("%d",&g.n);fprintf(fp,"%d",g.n);printf("请输入边数:");scanf("%d",&g.e);fprintf(fp,"%d",g.e);//初始化矩阵各元素值//读入边printf("请输入顶点信息:");//顶点的信息会出现

6、在矩阵边界上。fflush(stdin);//清空缓冲for(z=0;z

7、&w);fprintf(fp,"%d%d%d",a,b,w);g.edges[a][b]=w;g.edges[b][a]=w;}fclose(fp);}voidgetout_1()//文件载入函数{inti,a,b,w;FILE*fp;if((fp=fopen("record_1.txt","ab+"))==NULL){printf("不能打开文件");exit(0);}fscanf(fp,"%d",&g.n);fscanf(fp,"%d",&g.e);for(i=0;i

8、anf(fp,"%c",&g.vexs[i]);}for(i=0;i