三着色问题

代码来源：https://blog.csdn.net/queeniewsy/article/details/117430955
原理讲解：https://www.bilibili.com/video/BV1gL411C79e/?spm_id_from=333.337.search-card.all.click&vd_source=6a3bfbe95b8018e73e56fdbed87453e0

#include <iostream>
using namespace std;

//无向图G为上图a
int G[5][5] = { {0,1,1,0,0},
				{1,0,0,1,1},
				{1,0,0,1,1},
				{0,1,1,0,1},
				{0,1,1,1,0} };

bool iscolor(int k, int *color) {//判断是否为合法颜色
	for (int i = 0;i < 5 && i != k;i++) {//第k个顶点要跟前面k-1个已经选好颜色的顶点进行比较
		if (G[k][i] == 1 && color[k] == color[i])//如果两个顶点连通且颜色一样那就不行
			return false;
	}
	return true;
}

void output(int *color, int n) {//输出所有合法解
	for (int i = 0;i < n;i++)
		cout << color[i] << " ";
	cout << endl;
}

void graphcolor(int k, int *color) {
	for (int i = 1;i <= 3;i++) {//我们是三着色问题，所以只有三种颜色用于上色
		color[k] = i;//着色1，2，3
		if (iscolor(k, color)) {//合法解
			if (k == 4)//且完全上好(一组)色了，这里k=4就是5个顶点都上好色了
				output(color, 5);
			else//部分合法解
				graphcolor(k + 1, color);//到下一个顶点着色了
		}
	}
}


int main() {	
	//G的顶点的3着色
	int color[5];//( x0 , x1 , x2 , x3 , x4 )顶点i所着颜色xi
	for (int k = 0;k < 5;k++)
		color[k] = 0;

	graphcolor(0, color);//从0号顶点开始着色

	return 0;
}