地图着色问题实验报告

1算法设计与分析课程设计题目：地图着色问题文档：物联网工程学院物联网工程专业学号学生姓名班级二〇一三年十二月2一、问题描述：地图着色问题设计要求:已知中国地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少.二、概要设计（流程图）步骤：1．已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少；2．将各省进行编号，然后利用无向图的顶点之间的边来表示各省的相邻关系；3．将各编号进行逐一着色，利用循环语句遍历各省，判断语句判断是否符合要求；4．演示程序，以用户和计算机的对话方式进行；5．最后对结果做出简单分析及总结。流程图3三、源程序#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);}4return0;}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;}5}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)/*输出函数*/6{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);7PrintGraph(G);printf(着色方案:\n);trycolor(1,G);return0;}四、运行主要结果界面贴图1、中国地图简略图2、取地图一部分进行测试有6个顶点，8条边。各点相邻情况为：a-b,a-e,b-c,b-d,b-e,c-d,d-ee-f83、运行结果五、总结对中国地图着色即图着色问题，用m种颜色来为无向图着色，其中顶点个数为n。为此，用一个n元组来描述图的一种着色。在这种着色中，所有相邻的顶点都不会具有相同的颜色，这种着色就是有效着色。根据这种思想编写中国地图着色算法，算法主要使用回溯法。根据算法运行，可以看出，无论有多少点，点与点之间怎样相邻，都只需要4种颜色就可以完成着色。通过此次对中国地图着色问题的探究，我更好更深入了学习了着色问题中回溯法的运用，在课堂上学习的理论知识只有运用到实践里才能被更好的掌握。