地图着色课程报告材料

《地图着色课程报告材料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案课程设计报告学院、系：专业名称：计算机科学与技术课程设计科目VC++程序课程设计学生姓名：指导教师：完成时间：2013年12月精彩文档实用标准文案地图着色问题一、设计任务与目标地图上有不同国家（不同区域），每个国家都与其他一些国家邻接。现要求对地图着色，使所有的国家与它的邻接的国家有不同的颜色。通常由四种颜色就已足够。区域邻接区域123456021340312456041236051360613450二、方案设计与论证(1)可采取试探的方法逐步逼近最后解，即按某种模式生成一个部分解，

2、检查它是否合格。如为合格，在扩展这个部分解向最后解逼近，否则为不合格，不管如何扩展这个部分解都不会得到最后解。这时必须放弃已生成的部分解中的某些结果，“回朔”到先前的部分解，在生成一个部分解，直到获得最后解。也可采用递归算法，第一部先到底，再逐渐返回来各个判断，直到找出一组解并输出。(2)给定无向连通图G的邻接矩阵和m种不同的颜色。用这些颜色为图G的各个定点这着色，每个顶点着一种颜色。是否有一种颜色使G中的每条边的2个顶点着不同的颜色,使用if语句就能马上的判断出来。这个问题是图的m可着色判定问

3、题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同的颜色，则称这个数m为该图的色数。求有一个图的色数m的问题称为图的m可着色优化问题。(3)在算法Backtrack中，当t>n时，算法继续搜索，得到新的m着色方案，当前找到的可m着色方案数sum增1. 三、程序框图或流程图，程序清单与调用关系精彩文档实用标准文案四、全部源程序清单#includeclassColor{friendintmColoring(int,int,int**);private:boolOK(

4、intk);voidBacktrack(intt);精彩文档实用标准文案intn;//图的顶点数intm;//可用颜色数int**a;//图的邻接矩阵int*x;//当前的解longsum;//当前找到m种颜色的着色方案数public:Color();virtual~Color();};boolColor::OK(intk)//检查颜色可用性{for(intj=1;j<=n;j++){if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;}returntrue;}v

5、oidColor::Backtrack(intt)精彩文档实用标准文案{if(t>n){sum++;if(sum==1){for(inti=1;i<=n;i++){switch(x[i]){case1:cout<<"第"<

6、reak;}精彩文档实用标准文案}cout<

7、;//存放解的数组X.Backtrack(1);delete[]p;returnX.sum;}#include#include"olor.h"usingnamespacestd;intmain(){int**a;inti,j,b,c;cout<<"请输入邻接矩阵维数:"<>b;cout<>c;cout<

8、;i++)a[i]=newint[b];cout<<"请输入邻接矩阵数据:"<>a[i][j];}}cout<<"输入邻接矩阵的数据如下:"<