图的M着色算法演示

算法分析与设计实验报告第六次附加实验cout<<endl;}elsefor(int i=1;i<=m;i++){x[t]=i;if(ok(t)) Backtrack(t+1);//回溯，继续寻找下一层x[t]=0;//回到最初状态，使x[1]继续尝试其他填色的可能解}}测试结果当输入图如下时：结果如下：12435只要输入边即可当输入的图如下时：结果如下：附录：完整代码（回溯法）//图的m着色问题回溯法求解#include<iostream>using namespace std;class Color{friend void mColoring(int,int,int **);private:bool ok(int k);void Backtrack(int t);int n, //图的顶点个数m, //可用颜色数**a, //图的邻接矩阵*x; //当前解long sum; //当前已找到的可m着色的方案数};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++; //可行解+1cout<<"着色： ";for(int i=1;i<=n;i++) //输出可行解方案cout<<x[i]<<" ";cout<<endl;}elsefor(int i=1;i<=m;i++){x[t]=i;if(ok(t)) Backtrack(t+1);//回溯，继续寻找下一层x[t]=0;//回到最初状态，使x[1]继续尝试其他填色的可能解 }}void 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;cout<<"顶点： ";for(int i=1;i<=n;i++) //用于输出结果cout<<i<<" " ;cout<<endl;X.Backtrack(1); //从顶点1开始回溯delete []p;cout<<"解法个数："<<X.sum<<endl;}int main(){int n;int m;cout<<"please input number of node:";cin>>n;cout<<"please input number of color:";cin>>m;int **a=new int*[n+1];for(int i=0;i<=n;i++)a[i]=new int[n+1];for(int i=0;i<=n;i++) //利用抽象图实现图的邻接矩阵for(int j=0;j<=n;j++)a[i][j]=0;int edge;cout<<"please input adjacent edge number:";cin>>edge;int v,w;cout<<"please inout adjacent edge:"<<endl; //只要输入边即可for(int i=0;i<edge;i++){cin>>v>>w; //由于是无向图，所以对应的邻接矩阵对应的边都有，即v->m,m->v都有边a[v][w]=1;a[w][v]=1;}mColoring(n,m,a);system("pause");return 0;}。

图的着色问题一、题目简述(1) 图的m-着色判定问题给定一个无向连通图 G 和 m 种不同的颜色。

用这些颜色为图 G 的各顶点着色，每个顶点着一种颜色，是否有一种着色法使 G 中任意相邻的两个顶点着不同颜色？(2) 图的m-着色优化问题若一个图最少需要 m 种颜色才能使图中任意相邻的两个顶点着不同颜色，则称这个数 m 为该图的色数。

求一个图的最小色数 m 的问题称为m-着色优化问题。

二、算法思想1. m-着色判定问题总体思想：通过回溯的方法，不断为每一个节点着色，每个点的颜色由一个数字代表，初始值为1。

在对前面 step - 1 个节点都合法的着色之后，开始对第 step 个节点进行着色。

如果 n 个点均合法，且颜色数没有达到 m 种，则代表存在一种着色法使 G中任意相邻的两个顶点着不同颜色。

具体步骤：1. 对每个点 step ，有 m 种着色可能性，初始颜色值为1。

2. 检查第 step 个节点颜色的可行性，若与某个已着色的点相连且颜色相同，则不选择这种着色方案，并让颜色值加1，继续检查该点下一种颜色的可行性。

3. 如果第 step 点颜色值小于等于 m ，且未到达最后一个点，则进行对第 step + 1 点的判断。

4. 如果第 step 点颜色值大于 m ，代表该点找不到合适的分配方法。

此时算法进行回溯，首先令第 step 节点的颜色值为0，并对第 step - 1 个点的颜色值+1后重新判断。

5. 如果找到一种颜色使得第 step 个节点能够着色，说明 m 种颜色的方案是可行的。

6. 重复步骤2至5，如果最终 step 为0则代表无解。

2. m-着色优化问题基于问题1，对于一个无向图 G ，从1开始枚举染色数，上限为顶点数，第一个满足条件的颜色数即为所求解。

三、实现过程（附代码）1. m-着色判定问题#include<iostream>using namespace std;int color[100]; // 每个点的颜色int mp[100][100]; // 图的邻接矩阵int n, m, x; // n顶点，m种颜色方案，x条边bool check(int step) {// 判断与step点相邻的点，颜色是否与step点相同，若相同则返回falsefor (int i=1; i<=n; i++) {if (mp[step][i] ==1&&color[i] ==color[step]) {return false;}}return true;}bool Solve(int m) {// 求解是否可以找到一种可行的染色方案int step=1; // step指示当前节点while (step>=1) {color[step] +=1; // 假定颜色值从1开始，若为回溯，选择下一种方案while (color[step] <=m) { // 按照问题条件选择第step点颜色if (check(step)) {break;} else {color[step]++; // 搜索下一个颜色}}if (color[step] <=m&&step==n) { // 如果找完n个点，且染色方法小于等于m种 return true;} else if (color[step] <=m&&step<n) {step++; // 求解下一个顶点} else { // 如果染色数大于m个，回溯color[step] =0; // 回溯，该点找不到合适的分配方法，对上一点进行分析step--;}}// 如果step退到0，则代表无解return false;}int main() {int i, j;bool ans=false;cout<<"输入顶点数n和着色数m"<<endl;cin>>n>>m;cout<<"输入边数"<<endl;cin>>x;cout<<"具体输入每条边"<<endl;for (int p=0; p<x; p++) { // 以无向邻接矩阵存储边cin>>i>>j;mp[i][j] =1;mp[j][i] =1;}if (Solve(m)) {cout<<"有解";} else {cout<<"无解";}return0;}2. m-着色优化问题#include<iostream>using namespace std;int color[100]; // 每个点的颜色int mp[100][100]; // 图的邻接矩阵int n, m, x; // n顶点，m种颜色方案，x条边bool check(int step) {// 判断与step点相邻的点，颜色是否与step点相同，若相同则返回falsefor (int i=1; i<=n; i++) {if (mp[step][i] ==1&&color[i] ==color[step]) {return false;}}return true;}bool Solve(int m) {// 求解是否可以找到一种可行的染色方案int step=1; // step指示当前节点while (step>=1) {color[step] +=1; // 假定颜色值从1开始，若为回溯，选择下一种方案while (color[step] <=m) { // 按照问题条件选择第step点颜色if (check(step)) {break;} else {color[step]++; // 搜索下一个颜色}}if (color[step] <=m&&step==n) { // 如果找完n个点，且染色方法小于等于m种 return true;} else if (color[step] <=m&&step<n) {step++; // 求解下一个顶点} else { // 如果染色数大于m个，回溯color[step] =0; // 回溯，该点找不到合适的分配方法，对上一点进行分析step--;}}// 如果step退到0，则代表无解return false;}int main() {int i, j;bool ans=false;cout<<"输入顶点数n"<<endl;cin>>n;cout<<"输入边数"<<endl;cin>>x;cout<<"具体输入每条边"<<endl;for (int p=0; p<x; p++) { // 以无向图邻接矩阵存储边 cin>>i>>j;mp[i][j] =1;mp[j][i] =1;}for (m=1; m<=n; m++) { // 从小到大枚举着色数mif (Solve(m)) { // 如果有解，输出答案并跳出循环cout<<"最小色数m为 "<<m;break;}}return0;}四、结果及分析问题1测试用例：问题2测试用例：经检验，最少着色数的范围为2-4，意味着使 G 中任意相邻的两个顶点着不同颜色最多需要4种颜色。

《算法设计与分析》课程实验报告实验序号：10实验项目名称：实验十一回溯法（二）一、实验题目1.图的着色问题问题描述：给定无向连通图G和m种不同的颜色。

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

如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。

图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。

2.旅行商问题问题描述：给出一个n个顶点的带权无向图，请寻找一条从顶点1出发，遍历其余顶点一次且仅一次、最后回到顶点1的最小成本的回路——即最短Hamilton回路。

3.拔河比赛问题描述：某公司的野餐会上将举行一次拔河比赛。

他们想把参与者们尽可能分为实力相当的两支队伍。

每个人都必须在其中一只队伍里，两队的人数差距不能超过一人，且两队的队员总体重应该尽量接近。

4.批处理作业调度问题描述：给定n个作业的集合J=(J1,J2, .. Jn)。

每个作业J都有两项任务分别在两台机器上完成。

每个作业必须先由机器1处理，再由机器2处理。

作业i需要机器j的处理时间为tji(i=1,2, ..n; j=1,2)。

对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间，则所有作业在机器2上完成处理的时间和，称为该作业调度的完成时间和。

批处理作业调度问题要求，对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。

二、实验目的（1）通过练习，理解回溯法求解问题的解状态空间树与程序表达的对应关系，熟练掌握排列树、子集树的代码实现。

（2）通过练习，体会减少搜索解空间中节点的方法，体会解的状态空间树的组织及上界函数的选取对搜索的影响。

（3）通过练习，深入理解具体问题中提高回溯算法效率的方法。

（4）（选做题）：在掌握回溯法的基本框架后，重点体会具体问题中解的状态空间搜索时的剪枝问题。

三、实验要求（1）每题都必须实现算法、设计测试数据、记录实验结果，并给出时间复杂度分析。

四、实验过程（算法设计思想、源码）1.图的着色问题(1)算法设计思想用邻接矩阵a[i][j]存储无向图，对于每一个顶点有m种颜色可以涂。

图着⾊问题⼀、图着⾊问题（1）图的m可着⾊判定问题给定⽆向连通图G和m种不同的颜⾊。

⽤这些颜⾊为图G的各顶点着⾊，每个顶点着⼀种颜⾊。

是否有⼀种着⾊法使G中每条边的2个顶点着不同颜⾊。

（2）图的m可着⾊优化问题若⼀个图最少需要m种颜⾊才能使图中每条边连接的2个顶点着不同颜⾊，则称这个数m为该图的⾊数。

⼆、m可着⾊判定问题的解法【算法】（1）通过回溯的⽅法，不断的为每⼀个节点着⾊，在前⾯cur-1个节点都合法的着⾊之后，开始对第cur-1个节点进⾏着⾊，（2）这时候枚举可⽤的m个颜⾊，通过和第cur-1个节点相邻的节点的颜⾊，来判断这个颜⾊是否合法（3）如果找到那么⼀种颜⾊使得第cur-1个节点能够着⾊，那么说明m种颜⾊的⽅案在当前是可⾏的。

（4）cur每次迭代加1，如果cur增加到N并通过了检测，说明m种颜⾊是可满⾜的。

（5）注意，这⾥只是要求判断m种颜⾊是否可满⾜，所以找到任何⼀种⽅案就可以了。

【代码实现】#include<iostream>#include<cstring>using namespace std;const int maxn = 105;int G[maxn][maxn];int color[maxn];bool ans;int n,m,k;void init(){ans = 0;memset(G, 0 , sizeof G);memset(color, 0 , sizeof color);}void dfs(int cur){if(cur > n) {ans = 1;return;}for(int i=1; i<=m; i++){ //对cur结点尝试使⽤每⼀种颜⾊进⾏涂⾊bool flag = 1;//cur之前的结点必被涂⾊for(int j=1; j<cur; j++){if(G[j][cur] == 1 && color[j] == i){flag = 0;//只要有⼀个冲突都不⾏break;}}//如果可以涂上i颜⾊，则考虑下⼀个结点的情况if(flag){color[cur] = i;dfs(cur + 1);}//如果到这⼀步第cur个结点⽆法着⾊，则返回探寻其他⽅案else color[cur] = 0;//回溯 ;}}int main(){while(cin>>n>>k>>m){init();for(int i=1; i<=k; i++){int x,y;cin>>x>>y;G[x][y] = G[y][x] = 1;}dfs(1);cout<<ans<<endl;}return0;}三、m可着⾊拓展【问题】在上述基础上，求出m种颜⾊能够给图G涂⾊的总总⽅案数量【算法】由于这个时候要求总⽅案数量，所以在找到⼀种可⾏⽅案后，总是进⾏回溯再搜索其他的解决⽅案，与上⾯不同，上⾯是只需要找出⼀种⽅案即可，所以如果找到了就不需要再回溯了，所以在这⾥只需要把回溯语句的位置写到dfs语句的后⾯即可。

图着色问题的回溯算法●图着色问题的回溯算法：(非递归算法，求一个解)非递归算法：算法m-COLORING输入：正整数m, n和含n个顶点的无向连通图G的邻接矩阵graph。

输出: 图G的m着色问题的一个解x[1..n],若无解，则输出no。

solution。

flag=false //用flag标记问题是否有解。

k=1 ; x[1]=0while k>=1 and not flagwhile x[k]<="" not="" p="">x[k]=x[k]+1 //试将第k个顶点着下一种颜色。

if color(k) then //第k个顶点的当前颜色合法。

if k=n then flag=true //x[1..n]是一个解else //x[1..k]是部分解k=k+1 //准备对下一个顶点着色。

x[k]=0end ifend if //否则，剪枝end whilek=k-1//回溯end whileif flag then output x //输出一个解else output “no solution”//输出无解end m-COLORING过程color (k)//在前k-1个顶点已着色的情况下，判断第k个顶点是否可//着颜色x[k], 是则返回true, 否则返回false。

j=1while j<k< p="">if graph[k, j]*x[k]=x[j] thenreturn falseelse j=j+1end whilereturn trueend color递归算法：算法m-COLORING输入：正整数m, n和含n个顶点的无向连通图G的邻接矩阵graph。

输出: 图G的m着色问题的一个解x[1..n],若无解，则输出no。

flag=coloring( 1 )if flag then output x //输出一个解else output “No solution”//输出无解end NQUEENREC1过程coloring(k)//在前k-1个顶点已着色且满足着色条件的情况下，求图的// m着色问题的一个解，有解则返回true, 否则返回false。

算法设计与分析课程设计题目：用回溯法分析着色问题学院：理学院专业：信息与计算科学班级：09信科二班姓名：***学号: 200910010207用回溯法分析着色问题目录1 回溯法 (3)1.1回溯法的概述 (3)1.2 回溯法的基本思想 (3)1.3 回溯法的一般步骤 (3)2 图的m着色问题 (3)2.1图的着色问题的来源 (3)2.2通常所说的着色问题 (3)2.3图的着色问题描述 (3)2.4回溯法求解图着色问题 (5)2.5图的m可着色问题的回溯算法描述 (6)2.5.1回溯算法 (6)2.5.2 m着色回溯法递归 (8)2.5.3 m着色回溯法迭代 (9)2.5.4例题利用回溯法给图着色 (11)2.6复杂度分析着色回溯法迭代 (12)§1 回溯法1.1回溯法的概述回溯法是一种系统地搜索问题解的搜索算法。

它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。

算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。

如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。

否则，进入该子树，继续按深度优先的策略进行搜索。

回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。

而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。

这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

1.2回溯法的基本思想回溯法的基本思想是，在确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。

这个开始结点就成为一个活结点，同时也成为当前的扩展结点。

在当前的扩展结点处，搜索向纵深方向移至一个新结点。

这个新结点就成为一个新的活结点，并成为当前扩展结点。

如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。

换句话说，这个结点不再是一个活结点。