本文共 938 字，大约阅读时间需要 3 分钟。

图的m着色问题的问题提出是，给定图 和m种颜色，如下图所示，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。问是否有一种着色法使G中每条边的2个顶点着不同的颜色。采用回溯法判断该图的色数。

#include "stdafx.h" #include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int NUM = 12;int N, M;// 顶点个数和颜色数int g[NUM][NUM];//临接矩阵int color[NUM];//多少种涂色方式int solution_count = 0;//判断 g[k] 周围有没有 bool ok(int k) {
   	for (int j = 1; j <= N; ++j)	{
   		if (g[j][k] == 1 && color[k] == color[j]) return false;	}	return true;}void  DFS(int nodeV) {
   	if (nodeV > N) {
   		for (int i = 1; i <= N; ++i) cout << color[i] << " ";		//超出界限了		solution_count++;		cout << endl;		return;	}	for (int i = 1; i <= M; ++i) {
   		//m种颜色		color[nodeV] = i;		if (ok(nodeV)) DFS(nodeV + 1);		color[nodeV] = 0;	}}int main() {
   	cin >> N >> M;	int a, b;	while (cin >> a >> b &&a &&b) {
   		g[a][b] = g[b][a] = 1;	}	DFS(1);	cout << "\n total_solution = " << solution_count << endl;	getchar(), getchar();	return 0;}
      
     
    
   

转载地址：http://huyzi.baihongyu.com/