图的着色问题

借鉴自：https://www.cnblogs.com/czsharecode/p/10558732.html

一、图着色问题

（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种颜色是可满足的。

#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;
}
return 0;
}

图的着色问题

原文：https://www.cnblogs.com/hubowen1/p/12968633.html