龙岗网站建设-信科网络/域名访问网站入口

问题描述

给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果该图是m可着色的，找出所有不同的着色方案。

思路

图的m着色问题是找寻满足分配的可能方案，条件是，相邻结点之间不能同颜色。使用回溯法，对当前选择的结点，分别循环分配m中颜色，如果当前颜色合理，也就是跟相邻节点不一样，就继续下一个递归，否则，“保留现场”。当前递归的结点如果大于总节点数，那么就可以输出了，说明这是一个可行的配色方案。

C++

#include <iostream>
#include<bits/stdc++.h>
using namespace std;int n,m;//记录可能的次数
int cnt=0;
int G[20][20]= {0};
//记录谁涂的啥颜色，0代表没确定
int flag[20]= {0};//判断是否冲突
bool isok(int c)
{for(int k=1; k<=n; k++){if(G[c][k]&&flag[c]==flag[k]){return false;}}return true;
}void backtrack(int current)
{//终止条件if(current>n){for(int i=1; i<=n; i++){cout<<flag[i]<<" ";}cnt++;cout<<endl;}else{for(int i=1; i<=m; i++){flag[current]=i;//剪枝if(isok(current)){backtrack(current+1);}//保留现场flag[current]=0;}}
}int main()
{int tmp1,tmp2;cin>>n>>m;while(1){cin>>tmp1>>tmp2;if(tmp1==0&&tmp2==0){break;}G[tmp1][tmp2]=1;G[tmp2][tmp1]=1;}backtrack(1);cout<<cnt;return 0;
}