地图着色-数据结构

数据结构课程设计班级：学号：姓名：姓名：班级：学号：题目：地图着色一、需求分析：1.已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少；2.将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系；3.演示程序以用户和计算机的对话方式进行；4.最后对结果做出简单分析。二、概要设计：1）数据结构的设计typedefstruct//定义图{vextypevexs[MAXedg];//存放边的矩阵adjtypearcs[MAXedg][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)//输出函数{inti;for(i=1;i=G.vnum;i++)printf(%d,color[i]);printf(\n);}voidtrycolor(ints,GraphG)//s为开始图色的顶点{inti;if(sG.vnum)//递归出口{output(G);exit(1);}else{for(i=1;i=N;i++)//对每一种色彩逐个测试{color[s]=i;if(colorsame(s,G)==0)trycolor(s+1,G);//进行下一块的着色}}}2）源程序清单#includestdio.h#includestdlib.h#defineMAXedg100#defineMAX0#defineN4//着色的颜色数intcolor[30]={0};//来存储对应块的对应颜色typedefcharvextype;typedefintadjtype;typedefstruct//定义图{vextypevexs[MAXedg];//存放边的矩阵adjtypearcs[MAXedg][MAXedg];//图的邻接矩阵intvnum,arcnum;//图的顶点数和边数}Graph;//***********************************************************intLocateVex(GraphG,charu){inti;for(i=1;i=G.vnum;i++){if(u==G.vexs[i])returni;}if(i==G.vnum){printf(Erroru!\n);exit(1);}return0;}//**********************************************************voidCreateGraph(Graph&G)//输入图{inti,j,k,w;vextypev1,v2;printf(输入图的顶点数和边数:\n);scanf(%d%d,&G.vnum,&G.arcnum);getchar();printf(输入图的各顶点：\n);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表示):\n);for(k=0;kG.arcnum;k++){scanf(%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(图的各顶点：\n);for(i=1;i=G.vnum;i++)printf(%c,G.vexs[i]);printf(\n);printf(图的邻接矩阵：\n);for(i=1;i=G.vnum;i++){for(j=1;j=G.vnum;j++)printf(%d,G.arcs[i][j]);printf(\n);}}//******************************************************************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)//输出函数{inti;for(i=1;i=G.vnum;i++)printf(%d,color[i]);printf(\n);}//******************************************************************voidtrycolor(ints,GraphG)//s为开始图色的顶点，本算法从1开始{inti;if(sG.vnum)//递归出口{output(G);exit(1);}else{for(i=1;i=N;i++)//对每一种色彩逐个测试{color[s]=i;if(colorsame(s,G)==0)trycolor(s+1,G);//进行下一块的着色}}}//*****************************************************************intmain(){GraphG;CreateGraph(G);PrintGraph(G);printf(着色方案:\n);trycolor(1,G);return0;}四、测试结果：由于地图上各省连接关系太多，所以这里只给出简单的测试数据，来测试该程序的功能，如下：给出如下示意图，省份抽象为点，接壤抽象为有边相连。顶点为：abcdef相邻边：a-bb-cb-eb-fc-dc-ec-fe-f