图着色

#include <iostream>
using namespace std;


bool c[5][5];
int x[5];        
bool ok(int k,int n)
{
    int i;
    for(i=0;i<k;i++)
    if((c[k][i]&&x[k]==x[i]))
        return false;

    return true;
}

void m_coloring(int n,int m)//m限制颜色数

{
    int i,k;
    for(i=0;i<n;i++) //x[i]代表节点i的颜色

        x[i]=0;

    k=0;        
    while(k>=0)
    {
        x[k]++;
        while((x[k]<=m)&&(!ok(k,n)))
            x[k]++;
        
        if(x[k]<=m)
        {
            if(k==n-1)break;
            else k++;
        }
        else
        {
            x[k]=0;k--;
        }
    }
}
int main()
{

    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;

        m_coloring(5,3);
    for(i=0;i<5;i++)    
        cout<<i<<" :"<<x[i]<<endl;
    cout<<endl;
    return 0;
}



 

解题思路：

枚举每个顶点所代表的颜色，由于后涂的结点的颜色是从最初的颜色在与先前已涂结点的颜色比较不断更新而确定的，因此可以采用特殊的dfs搜索方法，即用while循环。