图着色.cpp

来自「这里面是很多经典算法的源代码」· C++ 代码 · 共 61 行

#include<stdio.h>
int a[21][21]={{0},{0,0,1,1,1,1},{0,1,0,1,1,1},{0,1,1,0,1,1},{0,1,1,1,0,1},{0,1,1,1,1,0}};
int colour[21];
int n=5;
int colourkind=1;
int flag;
int main()
{
	void search(int ,int );
	search(1,1);
}
int check(int i)
{
	int k;
	if(!colour[i])
	{
		return 0;
	}
	for(k=1;k<i;k++)
	{
		if(a[k][i]==1&&colour[k]==colour[i])
		{
			return 0;
		}
	}
	return 1;
}
void out()
{
	for(int i=1;i<=n;i++)
	{
		printf("%d ",colour[i]);
	}
}
void search(int i,int j)//i是从第i个顶点开始着色,j代表从第j种颜色开始着色
{
	int l;
	for(l=j;l<=colourkind;l++)
	{
		colour[i]=l;
		if(check(i))
		{
			if(i==n)
			{
				printf("\n");
				out();
				flag=1;//设定标志，假如已输出过一次，证明颜色种数已足够，colourkind不再更改
			}
			else
			{
				search(i+1,1);//若只想要一组解，只需加return;
			}
		}
	}
	if(!flag)
	{
		colourkind++;
		search(i,colourkind);
	}
}