数据结构课程设计报告地图着色问题

目录1 课题需求描述 (2)2 总体功能与数据结构设计 (2)2.1总体功能结构 (2)2.2数据结构设计 (3)3 算法设计和程序设计 (3)3.1算法设计 (3)3.1.1回溯法 (3)3.1.2贪心法 (6)3.2程序设计 (6)3.2.1调用回溯法，并判断着色方案是否可行 (6)3.2.2调用贪心法，对地图进行着色，并测试当前方案是否可行 (8)3.2.3在着色方案可行的情况下，换一种颜色着色，找出所有可行方案 (9)3.2.4主菜单的设计 (10)3.2.5二级菜单的设计 (11)3.2.6对菜单的使用及对算法用时的计时 (11)4 调试与测试 (14)5 设计总结 (17)5.1收获 (17)5.2存在问题 (18)6参考文献 (19)1 课题需求描述1.1地图着色问题设计要求：已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少地图着色问题是一个抽象的图形学问题，用程序实现对各个区域进行着色，并且相邻省所用的颜色不同，同时保证颜色的总数最少，如何将程序所需要的功能模拟着色在计算机中编程实现。

地图可以抽象为一个图，可以用邻接矩阵来进行模拟：对于每一个地图，我们可以把每一个区看作一个点，而区与区之间的邻接关系看作点与点之间的连线。

从而将地图抽象为一个图，然后就可以用邻接矩阵抽象。

相应的顶点为0，则表示两点邻接，否则，就不邻接，为1。

该程序用两种方法进行着色，分别是回溯法和贪心法。

2 总体功能与数据结构设计由于中国的省份较多，各省连接关系太多，所以程序只给出简单的测试数据，来测试该程序的功能。

程序对给定的程序进行着色，做到最多只用四种颜色进行着色，使得相邻省的颜色不同，并且将所有的着色可能都例举出来了。

对于地图得到着色，我用了两种算法，分别是回溯法和贪心法。

并且对他们的执行进行计时，比较他们的时间复杂度。

主要叙述：本课题设计的总体功能结构、数据结构设计。

2.1总体功能结构2.2数据结构设计void menu(); //主菜单void menu2(); //菜单用于选择算法void aboutjx(); //关于地图的说明void ljjz() //输出地图的邻接矩阵void huisu(int n,int m,int c[][12]) //调用回溯算法着色void tx(int map[N][N],int sum,int current) //调用贪心法着色int main() //输出主菜单，选择执行过程，对程序的调用3 算法设计和程序设计3.1算法设计3.1.1回溯法本程序采用回溯法进行着色。

一、课程背景着色问题是图论中的一个经典问题，也是计算机科学和数学中的一个重要课题。

着色问题旨在为图的顶点分配颜色，使得相邻的顶点颜色不同。

着色问题不仅具有理论意义，而且在实际应用中也有广泛的应用，如地图着色、VLSI设计、社会网络分析等。

本课程设计旨在让学生通过实践，深入理解着色问题的理论和方法，提高学生的编程能力和问题解决能力。

二、课程目标1. 理解着色问题的基本概念和性质；2. 掌握常用的着色算法及其实现；3. 能够分析和比较不同着色算法的效率；4. 培养学生运用所学知识解决实际问题的能力；5. 提高学生的编程能力和团队协作能力。

三、课程内容1. 着色问题的基本概念和性质- 图的定义和性质- 着色问题的定义和性质- 着色问题的分类2. 常用着色算法- 欧拉着色算法- 四色定理- 2-着色和3-着色算法- 胶囊算法3. 着色算法的实现- 图的表示方法- 着色算法的编程实现- 算法效率分析4. 着色问题的应用案例- 地图着色- VLSI设计- 社会网络分析四、教学方法1. 讲授法：系统讲解着色问题的基本概念、性质和常用算法；2. 讨论法：引导学生对着色问题进行深入探讨，分析不同算法的优缺点；3. 实验法：通过编程实践，让学生掌握着色算法的实现和效率分析；4. 案例分析法：结合实际应用案例，让学生了解着色问题的应用场景。

五、课程评价1. 课堂表现：参与讨论、提问和回答问题的积极性；2. 作业完成情况：按时完成作业，作业质量；3. 实验报告：实验报告的完整性和准确性；4. 课程设计：完成着色问题的解决方案，包括算法实现和效率分析；5. 期末考试：考察学生对着色问题理论知识的掌握程度。

六、课程时间安排1. 第一周：介绍着色问题的基本概念和性质；2. 第二周：讲解常用着色算法；3. 第三周：着色算法的实现和效率分析；4. 第四周：着色问题的应用案例；5. 第五周：课程设计和实验报告；6. 第六周：课程总结和期末考试。

课程设计报告课程设计题目：地图着色问题专业：xxxxxxxxx班级：xxxxxxxxx姓名：xxxxxxxxx一：需求分析：1)已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少；2)将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系；3)演示程序以用户和计算机的对话方式进行；4)最后对结果做出简单分析。

二：概要设计一：设计思路把34个省看成34个顶点，从选定的第一个顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。

着色过程就是一个递归的过程，直到所有的顶点都处理完后结束着色。

二：数据结构设计因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储。

其中：typedef struct ArcNode{int x; （表示与当前顶点所表示省份相邻的省份的位置信息）struct ArcNode *next; （指向下一个弧结点）}ArcNode; （表示省份之间相邻关系的弧结点）typedef struct{char *name; （顶点所表示的省份的名称）int color; （省份的颜色，用数字表示不同的颜色）ArcNode *firstnext; （指向第一个弧）}shengfen[35];三：详细设计该程序一共包含三个模版：分别为初始化模版、着色模版和输出模版。

1.初始化模块声明表示省份的顶点信息、省份之间相邻关系的弧的信息，并为其赋值。

2.着色模块为各个省份着色。

for(i=1;i<=34;i++){sheng[i].color=0;}for(i=1;i<=34;i++){j=1;p=sheng[i].firstnext;while(p!=NULL){while(p!=NULL&&j!=sheng[p->x].color){p=p->next;}if(p!=NULL)j++;}sheng[i].color=j;}3.输出模块输出各个省份的颜色信息。

地图着色问题课程设计一、课程目标知识目标：1. 理解地图着色问题的基本概念，掌握地图着色中涉及到的图论知识；2. 学会运用不同的算法解决地图着色问题，了解其优缺点；3. 掌握地图着色问题在实际生活中的应用，如行政区划、交通规划等。

技能目标：1. 能够运用所学知识，对给定的地图进行有效着色，提高解决问题的能力；2. 学会运用图论软件或工具进行地图着色的实际操作，培养动手实践能力；3. 通过团队合作，培养学生的沟通协调能力和解决问题的能力。

情感态度价值观目标：1. 激发学生对图论和地图着色问题的兴趣，培养良好的学习态度；2. 引导学生关注地图着色问题在实际生活中的应用，提高学生的社会责任感和实践意识；3. 培养学生面对复杂问题时，保持积极的心态，勇于克服困难，寻求解决问题的方法。

课程性质：本课程为数学学科选修课程，结合图论知识，以地图着色问题为载体，培养学生的逻辑思维能力和实际操作能力。

学生特点：学生处于高年级阶段，具备一定的数学基础和逻辑思维能力，对新鲜事物充满好奇心，具备一定的团队协作能力。

教学要求：注重理论与实践相结合，充分调动学生的积极性，引导学生主动参与课堂讨论和实践活动，提高学生的综合素养。

在教学过程中，将课程目标分解为具体的学习成果，以便于教学设计和评估。

二、教学内容1. 图论基础知识回顾：包括图的定义、图的表示方法、顶点和边的性质等；教材章节：第一章 图的基本概念2. 地图着色问题的提出：介绍地图着色的背景、意义及应用场景；教材章节：第二章 图的着色问题3. 地图着色算法：学习并掌握贪心算法、回溯算法、遗传算法等地图着色方法；教材章节：第三章 着色问题的算法及其应用4. 地图着色问题的实际操作：运用图论软件或工具进行地图着色实践；教材章节：第四章 着色问题的实际应用5. 地图着色问题案例分析：分析生活中的地图着色问题实例，如行政区划、交通规划等；教材章节：第五章 着色问题的案例分析6. 团队合作与交流：分组讨论、分享学习心得，培养学生的团队协作和沟通能力。

中国地图四色染色问题LtD中国地图四色染色问题一、问题描述将中国地图用四种不同的颜色红、蓝、绿、黄来染色，要求相邻的省份染色不同，有多少种不同的方案？二、问题分析本文将中国地图的34个省、直辖市、自治区、以及特别行政区转化为图论中的图模型。

其中每个省、市、自治区、特别行政区用图中的一个结点表示，两个结点间联通仅当两个板块接壤。

那么问题转化为图论中的染色问题。

由于海南、台湾省不与其它任何省份相邻，所以如果除海南、台湾外如果有n种染色方法，那么加上海南和台湾省后，有4*4*n种染色方法。

下面考虑除海南和台湾后的32个结点的染色方法。

三、中国地图染色方法采用分开海南和台湾省的分析方法，一方面的原因是除海南和台湾后的32个结点，可以组成一个联通图，因为海南省和台湾省不和任何其它省份邻接。

另一方面，我们建立一个联通图模型后，染色问题可以用深度优先遍历算法DFS，或者广度优先遍历算法BFS来解决，由于该方法的时间复杂度较高，属于暴力法，少考虑两个省份可以减少计算机处理此问题的时间。

本文采用DFS算法来解决这个染色问题。

3.1 DFS算法简介DFS算法是图的一种图的深度遍历算法，即按照往深的地方遍历一个图，假设到一个分支的尽头，那么原路返回到最近一个未被遍历的结点，继续深度遍历。

DFS遍历的具体步骤可为下：1）标记图中所有结点为“未访问〞标记。

2）输出起始结点，并标记为“访问〞标记3）起始结点入栈4）假设栈为空，程序结束；假设栈不为空，取栈顶元素，假设该元素存在未被访问的邻接顶点，那么输出一个邻接顶点，并置为“访问〞状态，入栈；否那么，该元素退出栈顶。

3.2 染色问题中的DFS算法设计我们先对任一结点染色，然后用DFS从该结点出发，遍历该图，遍历的下一结点颜色染为与之相邻的结点不同的颜色即可。

如果该结点无法染色那么回到上一个结点重新染色，直到所有的结点都被染色即可。

最后统计染色种数。

染色问题的算法伪代码可以描述如下：color_DFS(当前染色结点):for i in 所有颜色{ while j的已染色邻接点if 结点j相邻接点被染成i颜色标记并breakif 未被标记{当前结点染为i色if 当前结点为最后一个结点endelsecolor_DFS(next)｝}3.3 数据结构设计为了实现DFS染色算法，我们需要设计相应的数据结构。

课程设计地图的四色问题班级： 07计单组长：陈轶群组员：吕龙任课教师：鞠训光一、需求分析1．以二维数组list[N+1][N+1]表示地图，N表示区域数目，数组中以元素值为0表示不邻接，1表示邻接，限定区域数目N<=50.2．用户先输入区域数目N，再输入邻接区域的代码，邻接可只写一次，区域的代码为0～N,N个为区域，一个为外部区域，或输入N-1,则可不包括外部区域，N个区域由用户定义3．输出时，采用一一对应的方法，一个区域对应一种颜色形式：区域代码＝＝》颜色代码（1～4）＝》颜色4．本程序可为任意一张的地图染色，并且至多只染四种颜色5．测试数据：当区域数目N=8,地图如下：输出为 0=>1=>red1=>2=>green2=>3=>blue3=>4=>yellow4=>1=>red5=>2=>green6=>2=>green7=>4=>yellow8=>3=>blue6.程序执行的命令为：1）创建地图 2）存储地图 3）获取地图 4）地图着色 5）退出二、概要设计1．设定地图的抽象数据类型为：ADT list{数据对象：D={ai,j|ai,jε{’0’、‘1’}，0 <=i<=N,0<=j<=N数据关系：R={ROW,COL}ROW={<ai-1,j,ai,j>|ai-1,j,ai,jεD,i=1,…N,j=0,…,N}COL={<ai,j-1,ai,j>|ai,j-1,ai,jεD,i=0,…N,j=1,…,N}}2.本程序包括两个模块1）主程序模块：void main(){初始化；while{接受命令；处理命令；}}2）地图模块――实现地图抽象数据类型各模块之间的调用关系如下：主程序模块地图模块三、详细设计1.地图数据类型的操作设置如下：int creat(int N,int list[][MAX+1])//初始化并创建地图的邻接矩阵2.两点是否邻接的伪码算法：int link(int x,int *dc,int n,int list[][MAX+1]){//从1到n看是否与x相邻，是返回‘1’// 否则，返回‘0’for(i=0;i<n;i++)if(list[dc[i]][x])return(1);return(0);}3.着色伪码算法int *fco(int *color,int N,int list[][MAX+1]){//遇到一个区域，给它最小的颜色，看他是否与该种颜色的区域邻接，是则另赋//颜色，否则找下个区域，如果还不能着色，则前面区域另设颜色，直到成功初始化颜色for(i=0;i<N+1;i++){为第一个区域着色；for(k=0;k<4;k++){如果第k种颜色还未有地区，则将其赋予第i个区域；否则，看他是否与第k种颜色的地区相邻if(!link(i,dc[k],mcd[k],list)){dc[k][mcd[k]]=i;color[i]=k+1;mcd[k]=mcd[k]+1;break;}}if(color[i]==0)i=reset(i,color,mcd,dc,list);}}}4.将邻接矩阵存储伪码算法int save(int N,int list[][MAX+1]){//将邻接矩阵存成文件}5.主程序和其他函数的伪码算法void main{//主程序while(1){//系统初始化，主界面clrscr();//清屏显示清单ReadCommand(cmd); //读入一个操作命令符Interpret(cmd) ; //执行操作}}6.函数调用关系图反映了演示程序的层次结构1.Crea t2.save3.load4.fco5.exitlink四、调试分析1.首先使用了《离散数学》的解决方法，但在测试中国地图中出错，因为排序并不能解决递归调用的问题，后来省掉了排序，在使用开始那个例子时，第8个区域不能着色，因此，改采用递归的方法2.算法的时间复杂度为O(N),空间复杂度为O(N*N);3.通过本次试验，我认识到采用递归方法比较快捷，实现方便五、程序代码#include<graphics.h>#define MAX 50int total;int lin[MAX][MAX];int color[MAX];void draw();int okcyq(int dep,int i,int x){int k;for(k=x;k<=dep;k++){if(lin[dep][k]==1 && i==color[k])return(0);if(!okcyq(dep,i,k+1)&&k==dep)return(1);}return(0);}void output(){int k;for(k=1;k<=total;k++)printf("%d ",color[k]);}void find(int dep){int i;for(i=1;i<=4;i++){if(okcyq(dep,i,1)){color[dep]=i;if(dep==total) {output();getch();draw();exit(1);}else find(dep+1);color[dep]=0;}}}void draw(){int gdriver,gmode;int x=1,y=1,dx,dy,dx2,dy2,i=1;char dot,draw;gdriver=DETECT;initgraph(&gdriver,&gmode,"");cleardevice();setbkcolor(BLACK);while((dot=getch())!='q'){line(1,440,639,440);switch(dot){case 'a':setviewport(1,441,639,479,BLUE);clearviewport();outtextxy(1,2,"Press 'b' to end, then Press 'q' to quit");setviewport(1,1,639,439,BLUE);moveto(x,y);while((draw=getch())!='b'){switch(draw){case77:x=(getx()+1)%639;y=gety();moveto(x,y);putpixel(x,y,RED);break;case75:x=getx()-1;y=gety();moveto(x,y);putpixel(x,y,RED);break;case72:x=getx();y=gety()-1;moveto(x,y);putpixel(x,y,RED);break;case80:x=getx();y=(gety()+1)%439;moveto(x,y);putpixel(x,y,RED);break;}}break;default:setviewport(1,441,639,479,BLUE);clearviewport();outtextxy(1,2,"Press 'e' to end, then Press 'q' to quit");setviewport(1,1,639,439,BLUE);while((draw=getch())!='e'){switch(draw){case77:x=(getx()+1)%639;y=gety();putpixel(getx(),gety(),getpixel(x,y) );moveto(x,y);putpixel(x,y,YELLOW);break;case75:x=getx()-1;if(x==0)x=639;y=gety();putpixel(getx(),gety(),getpi xel(x,y));moveto(x,y);putpixel(x,y,YELLOW);break;case72:x=getx();y=gety()-1;if(y==0)y=439;putpixel(getx(),gety(),getpi xel(x,y));moveto(x,y);putpixel(x,y,YELLOW);break;case80:x=getx();y=(gety()+1)%439;putpixel(getx(),gety(),getpixel(x,y) );moveto(x,y);putpixel(x,y,YELLOW);break;}}}}setviewport(1,441,639,479,BLUE);clearviewport();outtextxy(1,2,"Press 'e' to end, then Press 'q' to quit");setviewport(1,1,639,439,BLUE);moveto(x,y);while((dot=getch())!='q'){switch(dot){case77:x=(getx()+1)%639;y=gety();putpixel(getx(),gety(),getpixel(x,y) );moveto(x,y);putpixel(x,y,YELLOW);break;case75:x=getx()-1;if(x==0)x=639;y=gety();putpixel(getx(),gety(),getpi xel(x,y));moveto(x,y);putpixel(x,y,YELLOW);break;case72:x=getx();y=gety()-1;if(y==0)y=439;putpixel(getx(),gety(),getpi xel(x,y));moveto(x,y);putpixel(x,y,YELLOW);break;case80:x=getx();y=(gety()+1)%439;putpixel(getx(),gety(),getpixel(x,y) );moveto(x,y);putpixel(x,y,YELLOW);break;case 13:dx=x;dy=y;{if(getpixel(dx,dy)!=RED)dx--;else break;}dx2=dx;dx=x;while(1){if(getpixel(dx,dy)!=RED)dx++;else break;}setcolor(color[i]);line(dx2+1,dy,dx-1,dy);dx=x;while(1){if(getpixel(dx,dy)!=RED)dy--;else break;}dy2=dy;dy=y;while(1){if(getpixel(dx,dy)!=RED)dy++;else break;}setcolor(color[i]);line(dx,dy2+1,dx,dy-1);break;case 'k':i++;}}closegraph();}void main(){int i,j,sp,ep;char c;clrscr();printf("The amount of district:");scanf("%d",&total);for(i=0;i<=total;i++)for(j=0;j<=total;j++)lin[i][j]=0;for(i=0;;i++){clrscr();printf("The start point:");scanf("%d",&sp);printf("The end point:");scanf("%d",&ep);lin[sp][ep]=1;lin[ep][sp]=1;printf("\nPress 'q' return to main...\n");c=getch();if(c=='q')break;}for(i=0;i<=total;i++)for(j=0;j<=total;j++){printf("%d ",lin[i][j]);if(j==total)printf("\n");}getch();for(i=0;i<=total;i++) color[i]=0;clrscr();find(1);}五、用户使用说明1.本程序的运行环境为Dos操作系统，执行文件为：no4.exe2.进入演示程序后，即显示文本方式的用户界面3.进入“创建地图”，即提示输入地区的数目，该命令后输入地图的数据4.进入save可把输入文件名，地图存储起来5.进入load 可输入文件名，把地图打印出来6.进入draw the color of graph，将地图进行染色六、测试结果1.输入地区数目为31 2 2 3 0 1 0 2 0 3输出0=〉1=〉red 1=>2=>green 2=>3=>blue 3=>2=>green七、附录着色后的中国地图。

课程设计(论文)任务书软件学院学院软件+电气专业2011— 3 班一、课程设计(论文)题目地图着色问题二、课程设计(论文)工作自2012 年 12 月 29 日起至 2013 年 1 月 6 日止三、课程设计(论文) 地点: 科技楼机房四、课程设计(论文)内容要求：1．本课程设计的目的⑴训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题；⑵初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；⑶提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。

2．课程设计的任务及要求1）基本要求：⑴要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告；⑵在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率；⑶程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释；⑷每位同学需提交可独立运行的程序和规范的课程设计报告。

2）课程设计论文编写要求⑴理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订；⑵课程设计报告（论文）包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等；⑶设计部分应包含系统功能模块图，调试分析应包括运行截图等。

3）课程设计评分标准：⑴学习态度：10分；⑵系统设计：20分；⑶编程调试：20分；⑷回答问题：20分；⑸论文撰写：30分。

4）参考文献：⑴严蔚敏,吴伟民. 数据结构(C语言版)[M]. 清华大学出版社. 2010.3⑵严蔚敏,吴伟民. 数据结构题集(C语言版)[M]. 清华大学出版社. 1999.2⑶何钦铭,冯燕等. 数据结构课程设计[M]. 浙江大学出版社. 2007.85）课程设计进度安排⑴准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料；⑵程序模块设计分析阶段（4学时）：程序概要设计、详细设计；⑶代码编写调试阶段（8学时）：程序模块代码编写、调试、测试；⑷撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文。

数据结构实验报告实验名称：地图染色问题学生姓名：刘健＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿班级：2013211129＿＿＿＿＿＿＿＿＿＿＿＿＿＿班内序号：10＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿学号：2013210796＿＿＿＿＿＿＿＿＿＿＿＿＿＿日期：2014/12/19＿＿＿＿＿＿＿＿＿＿＿＿＿1.实验目的目的：掌握图基本操作的实现方法了解最小生成树的思想和相关概念了解最短路径的思想和相关概念学习使用图解决实际问题的能力内容：对下图所示的地图进行染色，要求使用尽可能少的颜色进行染色，完成该算法。

测试数据：2. 程序分析2.1 存储结构二维数组struct NODE{int ID;int Links;}; 2.2 程序流程2.3 关键算法分析算法1：void SortNode(int b[][N],NODE SN[]) {for (int i=0;i<N;i++){SN[i].ID = i; SN[i].Links = 0; //初始化顶点信息for (int j=0;j<N;j++)SN[i].Links += b[i][j]; //计算每个顶点的度}for (int i=1;i<N;i++) //冒泡排序for (int j=0; j<N-i;j++)if (SN[j].Links<SN[j+1].Links){NODE tmp = SN[j];SN[j] = SN[j+1];SN[j+1] = tmp;}} [1] 算法功能：对邻接矩阵的顶点按度进行排序[2] 算法基本思想：计算每个顶点的度数，然后进行冒泡排序[3] 算法空间、时间复杂度分析：O（n^2）[4] 代码逻辑算法2：bool IsValid(int b[N][N], int k, int x[])//判断该颜色是否可用，b是邻接矩阵，k是当前染色的顶点序号，x是顶点颜色数组{for(int i=0; i<N; i++)if(!b[k][i])continue; //i和k不相邻，继续else if( x[k]== x[i])return false; //i和k相邻，并且颜色相同，该颜色不合适return true;}[1] 算法功能：判断相邻顶点的颜色是否重复[2] 算法基本思想：比较相邻顶点的颜色是否相同，相同的话返回值为false[3] 算法空间、时间复杂度分析：O（n）[4] 代码逻辑3．程序运行结果分析4．总结4.1实验的难点和关键点难点及关键点：对相邻顶点的颜色进行判断比较，如果相同则需要替换——用一个bool值来判断是否对颜色进行更改4.2心得体会通过这次的编程实验，我熟悉地掌握图基本操作的实现方法，了解了最小生成树的思想和相关概念，也明白了最短路径的思想和相关概念，并且学会了使用图解决实际问题，可谓受益匪浅。

地图着色问题说明：任何平面区域图都可以用四种颜色着色，使相邻区域颜色互异。

这就是四色定理。

要求给定区域图排出全部可能的四着色方案。

区域相邻关系用矩阵表示，每个区域又一个序号，（从0七连续排列）adj【i】【j勘硎厩 騣，j相邻。

数组cilir记录每个区域上着的色，用1.2.3.4表示。

程序应包括四个函数：coloring对所给邻接矩阵找着全部着色方案色乐的：对区域i在指定的颜色范围内选出可选颜色或报告失败（失败返回－1）辞令次日卡：判断对区域i在指定的颜色c是否可用八寸卡：选色失败时或完成一种着色方案时进行回溯另外可定义output函数，每次输出一种着色方案/*递归算法：void Coloring(区域 n)1. 令颜色集ClrSet={ 没有被区域n的邻居区域使用的颜色 }.2. 如果ClrSet是空集，返回.3. 对ClrSet中的每种颜色c，作循环：3.1 为区域n着色c。

3.2 如果所有区域都已着色(n是最后一个区域)，那么显示/保存着色结果.3.3 否则对下一个尚未着色的区域(n+1)，调用Coloring(n+1).4. 把区域n变为没有着色的区域.--------------------------------------------------------*/template<int node_count = 8>class CColoring{private:typedef int node_type;typedef int color_type;typedef std::set<node_type> node_set;typedef std::vector<color_type> color_array;public:void operator()(const int _Matrix[node_count][node_count]){matrix = _Matrix;colors_of_nodes.resize(node_count, 0); total_count = 0;coloring(0);}private:void coloring(node_type n){// 颜色的使用情况std::vector<bool> used_colors;node_type m;color_type c;// 初始化颜色的使用情况used_colors.resize(color_count, false);// 遍历每个与区域n相邻的区域mfor(m = 0; m < node_count; ++m){if(matrix[n][m]){// 获取m的颜色c = colors_of_nodes[m];// m已着色if(c != 0)used_colors[c] = true;}}// 遍历每个未被n的邻居使用的颜色cfor(c = 1; c < color_count; ++c){if(!used_colors[c]){// 为n着色ccolors_of_nodes[n] = c;// 着色完毕if(n >= node_count - 1)++total_count;// 输出结果_tprintf(_T("---------------------\n"));_tprintf(_T("Method %d:\n"), total_count);for(m = 0; m < node_count; ++m){_tprintf(_T("node: %d, color: %d\n"), m, colors_of_nodes[m]); }}// 还有区域没有着色else{// 为下一个未着色的区域，调用coloring()coloring(n + 1);}}}// 将n设置为没有着色的区域colors_of_nodes[n] = 0;}// 0表示无色，1-4表示4种不同颜色static const int color_count = 5;// 邻接矩阵const int (* matrix)[node_count];// 各区域对应的颜色color_array colors_of_nodes;// 总的着色方案数int total_count;};void main(){int Matrix[4][4] ={{ 0, 1, 0, 0 },{ 1, 0, 0, 0 },{ 0, 0, 0, 1 },{ 0, 0, 1, 0 },};CColoring<4> coloring;coloring(Matrix);}/*递归算法：void Coloring(区域 n)1. 令颜色集ClrSet={ 没有被区域n的邻居区域使用的颜色 }.2. 如果ClrSet是空集，返回.3. 对ClrSet中的每种颜色c，作循环：3.1 为区域n着色c。

数据结构课程设计报告地图着色问题地图着色问题是一个经典的图论问题，涉及到如何用最少的颜色给地图上的各个区域进行着色，使得相邻的区域颜色不同。

在数据结构课程设计报告中，我们将详细介绍地图着色问题的定义、解决方法以及实现过程。

一、问题定义地图着色问题可以用图论的方式来描述。

给定一个地图，地图上的每个区域可以看作图的一个顶点，而区域之间的邻接关系可以看作图的边。

问题的目标是找到一种着色方案，使得相邻的区域颜色不同，且使用的颜色数最少。

二、解决方法1. 贪心算法：贪心算法是一种简单而有效的解决地图着色问题的方法。

具体步骤如下：a. 选择一个未着色的区域。

b. 遍历该区域的所有邻接区域，记录已经使用的颜色。

c. 选择一个未使用的颜色，给该区域着色。

d. 重复步骤a-c，直到所有区域都被着色。

2. 回溯算法：回溯算法是一种穷举所有可能解的方法，通过逐步试错来找到最优解。

具体步骤如下：a. 选择一个未着色的区域。

b. 遍历所有可用的颜色，尝试给该区域着色。

c. 检查该区域与相邻区域的颜色是否冲突，如果冲突则回溯到上一步。

d. 重复步骤a-c，直到所有区域都被着色。

三、实现过程1. 数据结构设计：在解决地图着色问题时，我们可以使用图的邻接矩阵或邻接表来表示地图的结构。

邻接矩阵适用于稠密图，而邻接表适用于稀疏图。

此外，我们还需要使用一个数组来记录每个区域的颜色。

2. 算法实现：根据选择的解决方法，我们可以实现相应的算法来解决地图着色问题。

对于贪心算法，我们可以按照贪心的策略来选择颜色；对于回溯算法，我们可以使用递归来穷举所有可能的解。

3. 算法优化：地图着色问题属于NP完全问题，因此在实际应用中，对于大规模的地图，穷举所有可能的解是不可行的。

我们可以通过一些优化策略来提高算法的效率，如剪枝、启发式搜索等。

四、实例分析假设我们有一个地图，包含5个区域，相邻区域如下所示：区域1：区域2、区域3区域2：区域1、区域3、区域4区域3：区域1、区域2、区域4、区域5区域4：区域2、区域3、区域5区域5：区域3、区域4我们可以使用贪心算法来解决这个问题。

数据结构课程设计报告题目：地图着色一、需求分析1.问题描述现在有一张地图，为了便于区别各个地图上的版块，地图上相邻的颜色块应该是不同颜色。

现在的任务是给定一张地图，要对其进行着色，相邻版块之间颜色不能相同，输出最后的着色方案。

2.基本功能：功能一：为了程序的灵活性，可以让程序自由建立图。

功能二：对建好的图进行着色。

3.输入输出输入一张图的信息，正数输入边数和顶点数，输入边的关系，输入边的关系就是输入一条边的两个顶点。

颜色只用四种，所以每个结点的颜色域值只能取1到4输出时根据每个顶点不同的标号输出着色的结果。

二、概要设计1.设计思路给定四种颜色，从选定的第一个顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。

着色过程就是一个递归的过程，知道所有的顶点都处理完后结束着色。

2.数据结构设计：因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储。

抽象数据类型图的定义如下：数据对象V:V是具有相同特性的数据元素的集合，成为顶点集。

数据关系R：R={VR}VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在的路径}基本操作P:CreateGraph(&G)操作结果：创建一张需要操作的无向图GDestroy(Graph &G)初始条件：无向图G存在操作结果：销毁图GLocate(&G,i)初始条件：无向图G存在操作结果：若在图G中存在顶点i，则返回该顶点在图中的位置，否则返回其他信息Traverse(current, &G, store[])初始条件：无向图G存在，在图中有第current个顶点操作结果：对图开始遍历，并且用他们的序号在store数组的相应位置上存储所染上的颜色print(&G)初始条件：无向图G存在操纵结果：打印图G中每个顶点的颜色着色情况is_different(test, G )初始条件：无向图G存在，test为图中的一个顶点操作结果：如果图G中test的邻接顶点颜色都不与test相同，则返回真，否则返回假3.软件结构设计：本程序分为两个模块：1.主程序模块int main(){建立一张图G建立存储最终着色结果的数组对地图进行着色打印地图着色的情况销毁图退出}无向操作图模块 ---------- 无向图中结点的赋值，遍历三、详细设计#define MAX_NUM 30struct ArcNode{int data;ArcNode *arcnext;};typedef struct{int vexdata;Colour clo;ArcNode *firstnext;}VNode,Adjlist[MAX_NUM];typedef struct {Adjlist vexlist;int arcnum,vexnum;}Graph;图的基本操作：void CreateGraph(Graph& MyGraph)//创建一个要求的无向图int is_different(VNode test,Graph G )//如果结点test中的颜色和图G中和他相邻的结点颜色不同，返回TRUE，否则返回FALSE void Traverse(int current,Graph &G,int store[])//对图G进行遍历，并且将分配的颜色按他在邻接表中的位置赋值到store中相应的位置void Destroy(Graph &G)//销毁已经存在的无向图Gint Locate(Graph MyGraph,int signal)寻找无向图中顶点为i的结点，返回其位置以上重要函数的的伪码算法int is_different(VNode test,Graph G ){i=text.clofor(j=0;j<G.vexnum;j++){if(G.vexlist[j].clo=i)return FALSE;}return TRUE;}void Traverse(int current=1,Graph &G,int store[]) 主要函数其流程图如下：主要思想是遍历和递归void Destroy(Graph &G){for(i=0;i<G.vexnum;i++){ArcNode *p=G.vexlist[i].firstnext,*q;while(p){q=p->arcnext;free(p);p=q;}}}函数调用关系图：四、调试分析1.本程序的主要功能是自己建立一个图，然后对图进行着色，支持的数据类型是整形，用不同的数字表示不同的颜色。

c语言地图着色问题课程设计一、课程目标知识目标：1. 让学生掌握C语言中的基本数据结构与算法，特别是图的相关概念和应用。

2. 让学生理解地图着色问题的实质，即图的顶点着色问题，并掌握其与计算机科学中的其他问题的联系。

3. 让学生掌握利用C语言解决地图着色问题的算法设计，包括但不限于回溯法、贪心算法等。

技能目标：1. 培养学生运用C语言进行问题分析、算法设计和程序编写的能力。

2. 培养学生通过调试和优化程序来提高问题解决效率的技能。

3. 培养学生运用逻辑思维和数学方法解决实际问题的能力。

情感态度价值观目标：1. 培养学生对计算机科学的兴趣，特别是对算法和程序设计的热情。

2. 增强学生的团队合作意识，通过小组讨论和协作完成复杂问题的解决。

3. 引导学生认识到编程解决问题的实际意义，理解计算机技术在国家和社会发展中的重要作用。

课程性质分析：本课程设计属于高中信息技术课程中的编程模块，以C语言为载体，着重于算法思维和问题解决能力的培养。

学生特点分析：高中生在逻辑思维和抽象思维方面有较好的发展，能够理解较为复杂的问题和算法。

他们对新鲜事物充满好奇，但需要通过具体案例和实践活动来加深理解。

教学要求：1. 教学内容与课本紧密结合，注重理论与实践相结合。

2. 教学过程中要注重启发式教学，引导学生主动探索和思考。

3. 教学评价应关注学生在知识掌握、技能应用和情感态度方面的综合表现。

二、教学内容1. 图的基本概念：图的结构定义，图的分类（有向图与无向图，连通图与非连通图），图的表示方法（邻接矩阵和邻接表）。

2. 地图着色问题背景知识：介绍地图着色问题的实际意义，分析其与图论中的顶点着色问题的联系。

3. 算法原理：- 回溯法：介绍回溯法的基本思想，解决地图着色问题的应用。

- 贪心算法：讲述贪心算法的设计思路，及其在地图着色问题中的运用。

4. C语言实现：- 编写图的表示结构体和基本操作函数。

- 实现回溯法和贪心算法解决地图着色问题的C程序。

地图着色问题c语言课程设计一、课程目标知识目标：1. 理解地图着色问题的基本概念，掌握其数学模型及相关算法。

2. 掌握C语言中数组、循环、条件判断等基本语法结构，并能将其应用于解决地图着色问题。

3. 了解贪心算法、回溯算法等基本算法在地图着色问题中的应用。

技能目标：1. 能够运用C语言编写解决地图着色问题的程序，具备一定的编程实践能力。

2. 能够通过分析地图着色问题，设计合适的算法，培养问题解决和算法设计能力。

3. 能够运用所学知识解决类似地图着色问题的实际应用，具备一定的知识迁移能力。

情感态度价值观目标：1. 培养学生面对问题积极思考、主动探究的学习态度，增强自信心和自主学习能力。

2. 培养学生团队合作意识，学会在团队中沟通、协作、共同解决问题。

3. 激发学生对计算机科学的兴趣，认识计算机编程在解决实际问题中的价值。

课程性质：本课程为实践性较强的课程，以项目为导向，注重培养学生的编程实践能力和问题解决能力。

学生特点：学生具备一定的C语言基础，了解基本语法结构，但对算法设计和实际应用尚不熟悉。

教学要求：通过讲解、示范、实践等多种教学手段，使学生掌握地图着色问题的相关知识，培养其编程实践能力和问题解决能力。

同时，关注学生情感态度的培养，激发学习兴趣，提高自主学习能力。

在教学过程中，将目标分解为具体的学习成果，以便进行教学设计和评估。

二、教学内容1. 地图着色问题基础知识：- 图的基本概念和表示方法- 地图着色的数学模型- 地图着色问题的实际意义和应用2. C语言基础语法复习：- 数组的使用- 循环结构（for、while）- 条件判断（if、else）3. 算法设计与分析：- 贪心算法原理及在地图着色问题中的应用- 回溯算法原理及在地图着色问题中的应用- 算法复杂度分析4. 编程实践：- 使用C语言实现地图着色问题求解- 调试与优化程序- 团队合作完成项目任务5. 教学进度安排：- 第一周：地图着色问题基础知识、C语言语法复习- 第二周：贪心算法、回溯算法原理讲解及案例分析- 第三周：编程实践，团队协作完成地图着色问题求解- 第四周：项目展示、点评、总结教学内容参考教材相关章节，结合课程目标进行组织，保证教学内容科学性和系统性。

地图着色课程报告课程设计报告学院、系：专业名称：计算机科学与技术课程设计科目VC++程序课程设计学生姓名：指导教师：完成时间：2013年 12 月地图着色问题一、设计任务与目标地图上有不同国家（不同区域），每个国家都与其他一些国家邻接。

现要求对地图着色，使所有的国家与它的邻接的国家有不同的颜色。

通常由四种颜色就已足够。

区域邻接区域1 2 3 4 5 6 02 134 03 1 2456 04 1 2 3 6 05 1 36 06 1 3 4 5 0二、方案设计与论证(1)可采取试探的方法逐步逼近最后解，即按某种模式生成一个部分解，检查它是否合格。

如为合格，在扩展这个部分解向最后解逼近，否则为不合格，不管如何扩展这个部分解都不会得到最后解。

这时必须放弃已生成的部分解中的某些结果，“回朔”到先前的部分解，在生成一个部分解，直到获得最后解。

也可采用递归算法，第一部先到底，再逐渐返回来各个判断，直到找出一组解并输出。

(2)给定无向连通图G的邻接矩阵和m种不同的颜色。

用这些颜色为图G的各个定点这着色，每个顶点着一种颜色。

是否有一种颜色使G中的每条边的2个顶点着不同的颜色,使用if语句就能马上的判断出来。

这个问题是图的m可着色判定问题。

若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同的颜色，则称这个数m为该图的色数。

求有一个图的色数m的问题称为图的m可着色优化问题。

(3)在算法Backtrack中，当t>n时，算法继续搜索，得到新的m着色方案，当前找到的可m着色方案数sum增1.三、程序框图或流程图，程序清单与调用关系四、全部源程序清单#include<iostream>class Color{friend int mColoring(int,int,int **); private:bool OK(int k);void Backtrack(int t);int n;//图的顶点数int m;//可用颜色数int **a;//图的邻接矩阵int *x;//当前的解long sum;//当前找到m种颜色的着色方案数public:Color();virtual ~Color();};bool Color::OK(int k)//检查颜色可用性{for(int j=1;j<=n;j++){if((a[k][j]==1)&&(x[j]==x[k]))return false;}return true;}void Color::Backtrack(int t){if(t>n){sum++;if(sum==1){for(int i=1;i<=n;i++){switch(x[i]){case 1:cout<<"第"<<i<<"区域着红色"<<endl;break;case 2:cout<<"第"<<i<<"区域着蓝色"<<endl;break;case 3:cout<<"第"<<i<<"区域着绿色"<<endl;break;case 4:cout<<"第"<<i<<"区域着黄色"<<endl;break;}}cout<<endl;}}else{for(int i=1;i<=m;i++){x[t]=i;if(OK(t))Backtrack(t+1);x[t]=0;}}}int mColoring(int n,int m,int **a) {Color X;//初始化XX.n=n;//数组维数X.m=m;//可用颜色数X.a=a;//矩阵X.sum=0;//方案总数int *p=new int[n+1];for(int i=0;i<=n;i++)p[i]=0;X.x=p;//存放解的数组X.Backtrack(1);delete []p;return X.sum;}#include<iostream>#include"olor.h"using namespace std;int main(){int **a;int i,j,b,c;cout<<"请输入邻接矩阵维数:"<<endl; cin>>b;cout<<endl;cout<<"请输入使用颜色数目:"<<endl; cin>>c;cout<<endl;a=new int *[b+1];for(i=1;i<=b;i++)a[i]=new int[b];cout<<"请输入邻接矩阵数据:"<<endl; for(i=1;i<=b;i++){for(j=1;j<=b;j++){cin>>a[i][j];}}cout<<"输入邻接矩阵的数据如下:"<<endl;for(i=1;i<=b;i++){for(j=1;j<=b;j++){cout<<a[i][j]<<" ";}cout<<endl;}cout<<"Test:"<<endl;int temp=mColoring(b,c,a);cout<<"其中不同的配色方案总共有"<<temp<<"种"<<endl;delete []a;cout<<"四色定理:任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色."<<endl;system("pause");return 0;}五、程序运行的测试与分析六、结论与心得通过这次的课程设计的作业，我学到了许多的以前没有知识。

地图着色问题实验报告算法设计与分析课程设计题目：地图着色问题文档：物联网工程学院业学号学生姓名班级二〇一三年十二月一、问题描述：地图着色问题设计要求:已知中国地图, 对各省进行着色, 要求相邻省所使用的颜色不同, 并保证使用的颜色总数最少.二、概要设计（流程图）步骤：1．已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少；2．将各省进行编号，然后利用无向图的顶点之间的边来表示各省的相邻关系；3．将各编号进行逐一着色，利用循环语句遍历各省，判断语句判断是否符合要求；4．演示程序，以用户和计算机的对话方式进行；5．最后对结果做出简单分析及总结。

流程图三、源程序#include#include#define MAXedg 100#define MAX 0#define N 4 /*着色的颜色数*/int color[30]={0};/*来存储对应块的对应颜色*/ typedef char vextype;typedef int adjtype;typedef struct /*定义图*/{vextype vexs[MAXedg]; /*存放边的矩阵*/adjtype arcs[MAXedg][MAXedg]; /*图的邻接矩阵*/ int vnum,arcnum; /*图的顶点数和边数*/}Graph;int LocateVex(Graph G,char u){int i;for(i=1;iif(u==G.vexs[i])return i;}if(i==G.vnum){printf("Error u!\n");exit(1);}return 0;}void CreateGraph(Graph &G) /*输入图*/ {int i,j,k, w;vextype v1,v2;printf("输入图的顶点数和边数:\n"); scanf("%d%d",&G.vnum,&G.arcnum); getchar();printf("输入图的各顶点：\n");for(i=1;iscanf("%c",&G.vexs[i]);getchar();}for(i=0;ifor(j=0;jG.arcs[i][j]=MAX;printf("输入边的两个顶点和权值(均用1表示):\n"); for(k=0;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;}void PrintGraph(Graph G) /*输出图的信息*/{int i,j;printf("图的各顶点：\n");for(i=1;iprintf("%c ",G.vexs[i]);printf("\n");printf("图的邻接矩阵：\n");for(i=1;i{for(j=1;jprintf("%d ",G.arcs[i][j]);printf("\n");}}int colorsame(int s,Graph G)/*判断这个颜色能不能满足要求*/{int i,flag=0;for(i=1;iif(G.arcs[i][s]==1&&color[i]==color[s]){flag=1;break;}return flag;}void output(Graph G)/*输出函数*/int i;for(i=1;iprintf("%d ",color[i]);printf("\n");}void trycolor(int s,Graph G)/*s为开始图色的顶点，本算法从1开始*/{int i;if(s>G.vnum)/*递归出口*/{output(G);exit(1);}else{for(i=1;i{color[s]=i;if(colorsame(s,G)==0)trycolor(s+1,G);/*进行下一块的着色*/ }}}int main(){Graph G;CreateGraph(G);PrintGraph(G);printf("着色方案:\n");trycolor(1,G);return 0;}四、运行主要结果界面贴图1、中国地图简略图2、取地图一部分进行测试有6个顶点，8条边。

《数据结构》实验报告院系光电与信息工程学院专业电子信息工程姓名学号电话2011级2班2013年5月22日一、实验题目数据结构——期末综合实验——地图填色问题二、问题描述1976年。

美国科学家APPEL和HAKEN利用计算机证明了：对一张地图，可以用不超过4种颜色对其填色，使得相邻的区域填上不同的颜色。

要求输入一张行政区地图，用4种颜色对其填色，要求相邻的行政区域内没有相同的颜色，给出所有的填色方案，并统计方案个数。

三、数据描述首先考虑如何存储行政区域图，由于邻接矩阵能更好地描述各行政区之间的关系，所以采用邻接矩阵G来存储地图。

G[ I , J ]=1 表示I ，J 两个行政区域相邻，为0表示不相邻可采用二维数组来表示邻接矩阵G；另外设一数组COLOR[I]记录各行政区域所填颜色，分别取值为｛1（红色），2（黄色），3（蓝色），4（绿色）｝；数据描述如下：INT G[N][N];INT COLOR[N+1];四、概要设计（1）全局变量定义#define MAX_VERTEX_NUM 26 // 最大行政区域个数//------------------------------- 邻接矩阵数据类型的定义--------------------------------typedef struct{char vexs[MAX_VERTEX_NUM]; // 行政区域-顶点向量int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];// 邻接矩阵int vexnum; // 地图当前行政区域个数}Graph ;int Color[MAX_VERTEX_NUM+1]; // 地图行政区域填充的颜色存储数组long int Count=0; // 统计总共的填色方案个数（2）本程序主要包含6个函数：•主函数main()•创建地图及行政区域的邻接矩阵Create_Graph ()•显示行政区域的邻接矩阵关系Printf_Graph ()•对地图行政区域进行第一次着色Load_Color ()•对地图行政区域进行各种方案着色的显Print_Color ()•判断这个颜色对第n行政区域能不能满足要求Same_Color（）各函数间调用关系如下：Main（）Create_GraphPrintf_GraphLoad_ColorSame_Color（3）主函数的伪码main(){定义一个邻接矩阵G；创建地图及行政区域的邻接矩阵；显示行政区域的邻接矩阵关系；对地图进行填充颜色；改变颜色，显示多种方案；}五、详细设计//------------------------------- 邻接矩阵数据类型的定义--------------------------------#define MAX_VERTEX_NUM 26 // 最大行政区域个数typedef struct{char vexs[MAX_VERTEX_NUM]; // 行政区域-顶点向量int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵int vexnum; // 地图当前行政区域个数}Graph ;/**************************************************************************************** *函数：Create_Graph*功能：建立地图的邻接矩阵*说明：输入参数Graph *G本函数很好的完成了地图的创建以及行政区域之间的存储。

地图四色问题{问题描述：任何一张地图只要用四种颜色进行填涂，就可以保证相邻省份不同色}program tt;const num=20;var a:array [1..num,1..num] of 0..1;s:array [1..num] of 0..4; {用1-4分别代表RBWY四种颜色;0代表末填进任何颜色}k1,k2,n:integer;function pd(i,j:integer):boolean;{判断可行性：第I个省填上第J种颜色}var k:integer;beginfor k:=1 to i-1 do {一直从第一个省开始进行比较一直到I省减一的那个省，目的是对已经着色的省份来进行比较，因为>I的省还没有着色，比较没有意义，着色的顺序是先第一、二、三……I个省} if (a[i,k]=1) and (j=s[k]) then {省I和省J相邻且将填进的颜色和已有的颜色相同}beginpd:=false; {即不能进行着色}exit; {退出当前函数}end;pd:=true; {可以进行着色}end;procedure print;{打印结果}var k:integer;beginfor k:=1 to n do{将数字转为RBWY串}case s[k] of1:write('R':4);2:write('B':4);3:write('W':4);4:write('Y':4);end;writeln;end;procedure try(i:integer);var j:integer;beginfor j:=1 to 4 doif pd(i,j) then begins[i]:=j;if i=n then printelse try(i+1); {对下一个省进行着色}s[i]:=0; {不能进行着色，将当前状态设置0，即不进行着色}end;end;BEGINwrite('please input city number: '); readln(n);writeln('please input the relation of the cities:');for k1:=1 to n dobeginfor k2:=1 to n do read(a[k1,k2]); {A[K1，K2]=1表示省K1、K2相邻，为0就不相邻} readln;end;for k1:=1 to n do s[k1]:=0; {把所有的颜色设置为0，即还没有进行着色}try(1);END.。