地图着色课程报告.docVIP

课 程 设 计 报 告 学院、系： 专业名称： 计算机科学与技术 课程设计科目 VC++程序课程设计 学生姓名： 指导教师： 完成时间： 2013年 12 月 地图着色问题 一、设计任务与目标 地图上有不同国家（不同区域），每个国家都与其他一些国家邻接。现要求对地图着色，使所有的国家与它的邻接的国家有不同的颜色。通常由四种颜色就已足够。 区域 邻接区域 1 2 3 4 5 6 0 2 1 3 4 0 3 1 2 4 5 6 0 4 1 2 3 6 0 5 1 3 6 0 6 1 3 4 5 0 二、方案设计与论证 (1)可采取试探的方法逐步逼近最后解，即按某种模式生成一个部分解，检查它是否合格。如为合格，在扩展这个部分解向最后解逼近，否则为不合格，不管如何扩展这个部分解都不会得到最后解。这时必须放弃已生成的部分解中的某些结果，“回朔”到先前的部分解，在生成一个部分解，直到获得最后解。也可采用递归算法，第一部先到底，再返回来判断，找出一组解并输出。2)给定无向连通图G的邻接矩阵if语句就能马上的判断出来 (3)在算法Backtrack中，当tn时，算法继续有哪些信誉好的足球投注网站，得到新的m着色方案，当前找到的可m着色方案数sum增1.? 三、程序框图或流程图，程序清单与调用关系 四、全部源程序清单 #includeiostream 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(tn) { 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; } } coutendl; } } 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;//初始化X X.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; } #includeiostream #includeolor.h using namespace std; int main() { int **a; int i,j,b,c; cout请输入邻接矩阵维数:endl; cinb; coutendl; cout请输入使用颜色数目:endl; cinc; coutendl; 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++) { cina[i][j]; } } cout输入