图着⾊问题
⼀、图着⾊问题
（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语句的后⾯即可。
【代码实现】
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 105;
int G[maxn][maxn];
int color[maxn];
int 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++;
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);
cstring转为int
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可着⾊优化问题
【问题】给定⽆向图图G，顶点数N，边集E，要求⽤最少的颜⾊使得图中每⼀个顶点都涂上颜⾊，要求有边直接相连的顶点不能涂同样的颜⾊，问最少需要多少种颜⾊？
【算法】
（1）⼀种朴素的想法就是在上述图着⾊的结论基础上，使⽤⼆分法求出所需要的最⼩颜⾊数，范围1~N。但是存在⼤量的重复计算，复杂度过⾼。
（2）可以在之前的DFS上加上⼀维颜⾊数，⼀边增加顶点数⼀边增加颜⾊数，留下能够使得1~N顶点都满⾜的最少的颜⾊数
【题⽬链接】
题⽬⼤意是：有n个学⽣分考场，其中有k对学⽣认识，认识的学⽣不能在同⼀个考场，问最少需要多少个考场。
相当于有n个顶点，k条边，有边相连的顶点不能涂相同的颜⾊，问最少需要多少颜⾊。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 105;
const int inf = 0x3f3f3f3f;
int n,k;
int x,y;
int room[maxn];//room[i]表⽰i号房间的当前⼈数
int stu[maxn][maxn];//stu[i][j]表⽰第i个房间的第 j个学⽣是谁
int G[maxn][maxn];//存图
int ans ;
void init(){
memset(room ,  0, sizeof room);
memset(stu, 0,  sizeof stu);
memset(G,  0, sizeof G);
ans = inf;
}
//表⽰给第cur个学⽣安排房间
void dfs(int cur , int tot){
if(tot >= ans) return ;
//如果学⽣都安排好了，则记录这种⽅法所导出的ans
if(cur > n){
ans = min(ans , tot);
return ;
}
/
/如果还没安排好，则给cur合适的房间
for(int i=1; i<=tot; i++){
//看第i号房间⾥的所有⼈是否与其冲突
int len = room[i];
bool flag = 1;
for(int j=1; j<=len; j++){
if(G[stu[i][j]][cur]){
flag = 0;
break;
}
}
/
/如果到房间了就去安排下⼀个学⽣
if(flag){
room[i]++;//这个房间⾥多住了cur
stu[i][room[i]] = cur;
//继续深搜
dfs(cur+1, tot);
//回溯
stu[i][room[i]] = 0;
room[i]--;
}
}
/
/如果这 tot个房间都不⾏，则需要新开间房给这个学⽣
room[tot+1]++;
stu[tot+1][room[tot+1]] = cur;
//继续深搜
dfs(cur + 1 , tot + 1);
//回溯
stu[tot+1][room[tot+1]] = 0;
room[tot+1]--;
}
int main(){
while(cin>>n>>k){
init();
for(int i=1; i<=k; i++){
cin>>x>>y;
G[x][y] = G[y][x] = 1;
}
dfs(1,0);
cout<<ans<<endl;
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。