[数据结构与算法]回溯法C++ 图着色问题

**

回溯法C++ 图着色问题

**

问题描述：给定无向连通图G = (V, E)，求最小的整数m，用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。

对应算法实现：

int color[n];// Color[n]：n个顶点的着色情况
int arc[n][n];//arc[n][n]：顶点之间边的情况
void GraphColor (int m) {
	int i, k;
	for (i = 0; i < n; i++)
		color[i] = 0; //n个顶点初始着色均为0
	k = 0;
	while (k >= 0) {
		color[k]++; //取下一种颜色
		while (color[k] <= m) { //取到不冲突的颜色
			if (ok(k)) break;
			else color[k]++;
		}
		if (color[k] <= m && k == n - 1) {  //最后一个点时输出所有点的颜色并返回
			for (i = 0; i < n; i++)
				cout << color[i] << " ";
			return;
		}
		if (color[k] <= m && k < n - 1) //取下一个点
			k += 1;
		else //回溯
			color[k--] = 0;
	}
}
int ok(int i) {
	for (int j = 0; j < n; j++) 
		if (arc[i][j] == 1 && color[i] == color[j]) return 0;
	return 1;
}