图着色问题.c

图着色问题的回溯算法

#include <iostream>
using namespace std;
bool ok(int x[],int k,bool c[5][5],int n) //判断对顶点k着色以后是否合法着色
{
int i;
for(i=0;i<k;i++)
if((c[k][i]&&x[k]==x[i]))
return false;
return true;
}
//输入n为顶点个数，颜色数m，图的邻接矩阵c[][]
//输出n个顶点的着色x[]
void m_coloring(int n,int m,int x[],bool c[5][5]) 
{
int i,k;
for(i=0;i<n;i++)
x[i]=0;
k=0;
while(k>=0)
{
x[k]++;
while((x[k]<=m)&&(!ok(x,k,c,n)))
x[k]++;
if(x[k]<=m){
if(k==n-1)break;
else k++;
}
else
{
x[k]=0;k--;
}
}
}
int main()
{
bool c[5][5];
int i,j;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
c[i][j]=false;
c[0][1]=true;
c[0][2]=true;
c[1][2]=true;
c[1][3]=true;
c[1][4]=true;
c[3][4]=true;
c[2][4]=true;

c[1][0]=true;
c[2][0]=true;
c[2][1]=true;
c[3][1]=true;
c[4][1]=true;
c[4][3]=true;
c[4][2]=true;
int x[5];
m_coloring(5,3,x,c);
for(i=0;i<5;i++)
cout<<x[i]<<" ";
cout<<endl;
return 0;


}