//3着色问题，输出所有可能解，

 

#include
using namespace std;
int Adjacent[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}};//邻接矩阵，存放初始数据，这里用5×5的矩阵进行测试
int c[5]={0};//全局变量,默认初始化为0
bool flag=false;
 
int IsLegal(int n)//判断两个点是否邻接，并且着的颜色是否一样
{
 for(int i=0;i<=n;i++)//k保证不会出现c[i]=c[j]=0比较的情况
  for(int j=i+1;j<=n;j++)
   if(  Adjacent[i][j]==1 && c[i]==c[j])
   { return false;}
   return true;
}
void graphcolor(int l)//递归调用函数
{
 for(int i=1;i<=3;i++)
 {
  c[l]=i;
  if(l==4&&IsLegal(l))//如果是合法着色则输出
  {
   flag=true;
    for(int i=0;i<5;i++)
   cout<<c[i]<<" ";
    cout<<endl;
  }
  else
  {
   if(IsLegal(l))//如果是部分着色，进行递归
    graphcolor(l+1);
  }
 }
}
void Color()
{
 flag=false;
 graphcolor(0);//
 if(!flag)
 {
  cout<<"no solution"<<endl;
 }
}
int main()
{
 Color();
}

赞0 2658次