第五章 图着色问题

#include <iostream>
#include <cstring>
using namespace std;

#define N 8

//表示一张图
int g[][N]={
	{0,1,1,1,0,0,1,0},
	{1,0,1,1,1,0,0,0},
	{1,1,0,0,1,1,0,0},
	{1,1,0,0,1,0,1,0},
	{0,1,1,1,0,1,1,1},
	{0,0,1,0,1,0,0,1},
	{1,0,1,1,1,0,0,1},
	{0,0,0,0,1,1,1,0}
};
//标记的颜色
int color[N];

//检查是否有邻居标记过同一种颜色
int ok(int t){
	for(int i=0;i<N;i++)
		if(i!=t&&g[t][i]&&color[t]==color[i])
			return 0;
	return 1;
}
//试着用m种颜色进行标记
bool traceback(int t,int m){
	if(t>=N)return true;

	for(int i=1;i<=m;i++){
		color[t]=i;
		if(ok(t)&&traceback(t+1,m))return true;
		color[t]=0;
	}
	return false;
}
int main()
{
#ifndef wangchuan
	freopen("C:\\in.txt","r",stdin);
#endif // !wangchuan
	
	memset(color,0,sizeof(color));
		
	for(int j=1;j<=4;j++){
		if(traceback(0,j)){
			for(int i=0;i<N;i++){
				cout<<"第"<<i<<"点标记颜色"<<color[i]<<endl;
			}
			break;
		}
	}
	return 0;
}

//图着色问题
//贪心法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 8

//表示一张图
int g[][N]={
	{0,1,1,1,0,0,1,0},
	{1,0,1,1,1,0,0,0},
	{1,1,0,0,1,1,0,0},
	{1,1,0,0,1,0,1,0},
	{0,1,1,1,0,1,1,1},
	{0,0,1,0,1,0,0,1},
	{1,0,1,1,1,0,0,1},
	{0,0,0,0,1,1,1,0}
};

int color[N];

//检查是否有邻居标记过颜色k
int ok(int t,int k){
	for(int i=0;i<N;i++)
		if(i!=t&&g[t][i]&&k==color[i])
			return 0;
	return 1;
}

void Greedy(){
	color[0]=1;//先给节点0着颜色1

	int k = 0;//K 代表第几种颜色
	while (true) {
		k++;
		//如果所有顶点均着色，退出循环
		int i;
		for(i=1;i<N;i++)if(!color[i])break;
		if(i==N)break;
		//

		for(int i=1;i<N;i++){
			if(color[i])continue;
			//判断i点能否着颜色k，即i的邻居节点没有着颜色k的
			if(ok(i,k))color[i]=k;
		}
	}
}
int main()
{
#ifndef WANGCHUAN
	freopen("C:\\in.txt","r",stdin);
#endif // !WANGCHUAN
	memset(color,0,sizeof(color));
	Greedy();

	for (int i=0; i<N; i++)
		cout<<"第"<<i<<"点标记颜色"<< color[i] <<endl;
	return 0;
}