C++和数据结构课程设计报告 中南大学

C++和数据结构课程设计题目名称:地图着色问题TOC\o"1-5"\h\z姓 名学 号专 业班 级指导教师编写日期2017・7・1二、目录TOC\o"1-5"\h\z问题描述 2系统设计 4\o"CurrentDocument"源代码清单 7\o"CurrentDocument"运行结果测试与分析 10结论与心得 12三、正文部分1、问题描述（1） 题目：设计地图着色软件，对湖南省地图中的地级市进行着色，要求相邻地级市所使用的颜色不同，并保证使用的颜色最少。（2） 题目分析：由地图着色问题很容易想到图的着色问题，因此可以把地图抽象为无向图来解决地图的着色问题。题目以湖南省地图为实际应用载体，其本质是图着色问题（GraphColoringProblem,GCP）又称着色问题，是最著名的NP-完全问题之一。对地图的抽象相当于对图的抽象，即以邻接矩阵来实现地图的区域相邻的描绘，而对地图的区域数即以图的顶点数来描绘。具体是将湖南省各个地级市进行编号，然后利用无向图各个顶点之间的边来表示各省的相邻关系。地图着色问题与著名四色定理：四色定理是一个著名的数学定理：如果在平面上划出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样；另一个通俗简洁的说法是：每个地图都可以用不多于四种颜色来染色，而且不会有两个邻接的区域颜色相同。这就是著名的四色定理，由四色定理可以想到只需要四种颜色就可以为一个区域的地图着上颜色，而且相邻区域的颜色不相同。（3） 基本要求：地图采用图型数据结构，每个地级市为一个节点，边表示对应的两个地级市相邻；设计着色算法，保证邻接点不是同一种颜色；演示程序以用户和计算机的对话方式进行。（4） 问题解决：计算机中，图主要可以用两种方法表示：邻接矩阵和邻接链表。N个顶点的邻接矩阵是一个N*N的布尔矩阵，图中的每一个顶点都由一行或者一列来表示，如果从第i个顶点和第j个顶点之间有边连接，则矩阵第i行，第j列的元素等于1，如果没有边连接，则等于0，这就是图的邻接矩阵表示，那么地图也可以抽象为一个图，其可以用邻接矩阵来进行模拟：对于每一个地图，我们可以把每一个区〔区域或国家）看作一个点，而区与区之间的邻接关系看作点与点之间的连线。从而将地图抽象为一个图，然后就可以用邻接矩阵抽象。如下图：AB

AB其邻接矩阵为:ABCDEA01100B10111C11001D01001E01111目的：掌握图基本操作的实现方法，了解递归的思想和相关概念，了解最短路径的思想和相关概念，学习使用图解决实际问题的能力。2、系统设计（1） 总体分析设计：已知湖南省地图，将各地级市进行编号，然后利用无向图顶点之间的边来表示各省的相邻关系，创建图的操作，采用图状的逻辑结构，存储结构选用邻接矩阵。首先把14个地级市看成14个顶点，从选定的一号顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。着色过程以一个递归的过程进行，直到所有的顶点都处理完后结束着色。（2） 数据结构的设计：typedefstruct//定义图（vextypevexs[MAXedg];//存放边的矩阵adjtypearcs[MAXedg][MAXedg];//图的邻接矩阵intvnum,arcnum; //图的顶点数和边数}Graph;（3） 给出如下湖南省地图，省份抽象为点，接壤抽象为有边相连。得到如下顶点的边关系：（注：a为湘西土家族苗族自治州，b为张家界市，c为常德市，d为岳阳市，e为怀化市，f为益阳市，g为长沙市，h为娄底市，i为湘潭市，j为邵阳市，k为株洲市，l为衡阳市，m为永州市，n为郴州市）ab1ae1be1bc1ec1cd1cf1df1dg1ef1fg1eh1ej1hf1hg1hj1hi1hl1gi1ik1gk1il1jl1kl1jm1ml1kn1ln1mn1功能模块的划分及模块间调用关系:dpQ~eateGraphD—,PrintGraphOLLocateVeocCtrJtmlQirO-i s^G.vnum，-s-^G.vnumoutput^colorsarneO着色模块：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(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);//进行下一块的着色}}}3、源代码清单#include<stdio.h>#include<stdlib.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;k<G.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(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);//进行下一块的着色}}}intmain()(GraphG;CreateGraph(G);PrintGraph(G);printf("湖南省地图的着色方案为:\n");trycolor(1,G);return0;}4、运行结果测试与分析e1e1'C:\Users\AdministratorXDe§lrtop\-果程设计Debug\l.exe'QQQQn180QQ00QQ0010Q1110111010101111110Q011001001100110001S10Q101001010000001i~11000000010100000000114e1e1'C:\Users\AdministratorXDe§lrtop\-果程设计Debug\l.exe'QQQQn180QQ00QQ0010Q1110111010101111110Q011001001100110001S10Q101001010000001i~11000000010100000000114*注1：a为湘西土家族苗族自治州，b为张家界市，c为常德市，d为岳阳市，e为怀化市，f为益阳市，g为长沙市，h为娄底市，i为湘潭市，j为邵阳市，k为株洲市，l为衡阳市，m为永州市，n为郴州市*注2：1为黄色，2为红色，3为绿色，4为蓝色输入边的关系，分别用黄红绿蓝四色为湖南省地图着色，根据程序输出结果手动为湖南省第十页共十三页地图作色，得到简易着色图如下所示，如图所示可知程序运行结果为正确:五、结论与心得用最少的颜色对地图进行着色，达到相邻区域的颜色不相同，本次课设利用了无向图顶点之间的边来表示各省的相邻关系，创建图的操作，采用图状的逻辑结构，存储结构选用邻接矩阵，着色过程以一个递归的过程进行，直到所有的顶点都处理完后结束着色，完成问题的解决。通过此次课程设计，对图的操作与理解