欢迎来到天天文库
浏览记录
ID:15311193
大小:495.50 KB
页数:7页
时间:2018-08-02
《地图着色课程设计》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、数据结构课程设计题目地图着色问题姓名杨康林伟胜学号130910121309101209年级09级专业信息与计算科学指导教师熊保平年月日题目:地图着色一、需求分析:1.已知中国地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少;2.将各省进行编号,然后利用无向图个顶点之间的边来表示各省的相邻关系;3.演示程序以用户和计算机的对话方式进行;4.最后对结果做出简单分析。二、概要设计:1)数据结构的设计typedefstruct//定义图{vextypevexs[MAXedg];//存放边的矩阵adjtypearcs[MA
2、Xedg][MAXedg];//图的邻接矩阵intvnum,arcnum;//图的顶点数和边数}Graph;2)功能模块的划分及模块间调用关系三、详细设计:1)主要功能模块的算法思想及其步骤着色模块:intcolorsame(ints,GraphG)//判断这个颜色能不能满足要求{inti,flag=0;for(i=1;i<=s-1;i++)//分别与前面已经着色的几块比较if(G.arcs[i][s]==1&&color[i]==color[s]){flag=1;break;}returnflag;voidoutput(GraphG)/
3、/输出函数{inti;for(i=1;i<=G.vnum;i++)printf("%d",color[i]);printf("");}voidtrycolor(ints,GraphG)//s为开始图色的顶点{inti;if(s>G.vnum)//递归出口{output(G);exit(1);}else{for(i=1;i<=N;i++)//对每一种色彩逐个测试{color[s]=i;if(colorsame(s,G)==0)trycolor(s+1,G);//进行下一块的着色}}}1)源程序清单#include#in
4、clude#defineMAXedg100#defineMAX0#defineN4//着色的颜色数intcolor[30]={0};//来存储对应块的对应颜色typedefcharvextype;typedefintadjtype;typedefstruct//定义图{vextypevexs[MAXedg];//存放边的矩阵adjtypearcs[MAXedg][MAXedg];//图的邻接矩阵intvnum,arcnum;//图的顶点数和边数}Graph;//*****************************
5、******************************intLocateVex(GraphG,charu){inti;for(i=1;i<=G.vnum;i++){if(u==G.vexs[i])returni;}if(i==G.vnum){printf("Erroru!");exit(1);}return0;}//**********************************************************voidCreateGraph(Graph&G)//输入图{inti,j,k,w;vextypev1
6、,v2;printf("输入图的顶点数和边数:");scanf("%d%d",&G.vnum,&G.arcnum);getchar();printf("输入图的各顶点:");for(i=1;i<=G.vnum;i++){scanf("%c",&G.vexs[i]);getchar();}for(i=0;i<=G.vnum;i++)for(j=0;j<=G.vnum;j++)G.arcs[i][j]=MAX;printf("输入边的两个顶点和权值(均用1表示):");for(k=0;k7、%c",&v1);getchar();scanf("%c",&v2);getchar();scanf("%d",&w);getchar();i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=w;}}//****************************************************************voidPrintGraph(GraphG)//输出图的信息{inti,j;printf("图的各顶点:");for(i=1;i<=8、G.vnum;i++)printf("%c",G.vexs[i]);printf("");printf("图的邻接矩阵:");for(i=1;i<=G.vnum;i++){for(j=
7、%c",&v1);getchar();scanf("%c",&v2);getchar();scanf("%d",&w);getchar();i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=w;}}//****************************************************************voidPrintGraph(GraphG)//输出图的信息{inti,j;printf("图的各顶点:");for(i=1;i<=
8、G.vnum;i++)printf("%c",G.vexs[i]);printf("");printf("图的邻接矩阵:");for(i=1;i<=G.vnum;i++){for(j=
此文档下载收益归作者所有