graphcolor.cpp

图着色问题得Visual C++ 代码

#include "stdio.h"
int c[6][6];    //数组c[n+1][n+1]存储顶点之间边的情况
int n=5;        //n个顶点
int color[6];   //数组color[n+1]表示顶点的着色情况
int m=3;        //m种颜色
bool OK(int k); 
  

void main()
{
	//初始化边的情况
	c[1][2]=c[2][1]=1;c[1][3]=c[3][1]=1;
	c[2][3]=c[3][2]=1;c[2][4]=c[4][2]=1;c[2][5]=c[5][2]=1;
	c[3][5]=c[5][3]=1;
	c[4][5]=c[5][4]=1;

    for(int i=1;i<=n;i++)
		color[i] = 0;
	int k = 1;
	while(k>=1)
	{
		color[k]+=1;
		while(color[k]<=m)
			if(OK(k))   break;
			else     color[k]+=1; //搜索下一个颜色
        if(k==n&&color[k]<=m)     //搜索完毕，输出解
		{
			for(i=1;i<=n;i++)
				printf("%d\n",color[i]);
			return;
			//break;
		}
		else
		{
			if(k<n&&color[k]<=m)
				k=k+1;      //处理下一个顶点
			else
			{
				color[k]=0;k=k-1;//回溯
/*				if(k==0)
				{
					printf("NO Answer!");
					break;
				}
			*/
			}
		}
	}
	printf("No Answer!");
}

bool OK(int k)   //判断定点k的着色是否发生冲突
{
	for(int i=1;i<=n;i++)
		if(c[k][i]==1&&color[i]==color[k]) return false;
	return true;
}