图的m-着色判定问题——给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色?
图的m-着色优化问题——若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的最小色数m的问题称为m-着色优化问题。
解题思路：使用回溯法，具体步骤是将cur=1传入backtrack（），即从第一个开始涂色。
涂的时候从颜色1开始到m，每当涂上一个色，要用ok（cur）判断第cur个点是否可以涂这个色，不可以的话就不再往下涂了，改试另一个颜色，可以的话就继续。
当cur>n的时候即前n个点都涂完了，然后输出结果并cou++计数。
#include <iostream> #include <cstdio> using namespace std; int n,m; int a=1,b=1; int cou=0; int graph[20][20]={0}; int color[20]={0}; bool ok(int c){ for(int k=1;k<=n;k++){ if(graph[c][k]&&color[c]==color[k]){ return false; } } return true; } void backtrack(int cur){ if(cur>n){ for(int i=1;i<=n;i++){ printf("%d ",color[i]); } cou++; printf("\n"); }else{ for(int i=1;i<=m;i++){ color[cur]=i; if(ok(cur)){ backtrack(cur+1); } color[cur]=0; } } } int main() { scanf("%d %d",&n,&m); while(scanf("%d %d",&a,&b)!=EOF&&a!=0&&b!=0){ graph[a][b]=1; graph[b][a]=1; } backtrack(1); printf("Total=%d",cou); return 0; }
原文：http://www.cnblogs.com/Bennetts/p/6506483.html