m着色问题

图的m-着色判定问题——给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色?

图的m-着色优化问题——若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的最小色数m的问题称为m-着色优化问题。

算法思路：

color[n] 存储 n个顶点的着色方案，可以选择的颜色为

1 到 m

t=1 对当前第t个顶点开始着色：

若t>n  则已求得一个解，输出着色方案即可

否则，依次对顶点t着色1到m，

   若t与所有其它相邻顶点无颜色冲突，则继续为下一顶点着色；否则，回溯，测试下一颜色。

/*========================================================================
#   FileName: color_painting_2.cpp
#     Author: zhuyupeng
#      Email: ypzhu1015@gmail.com
#   HomePage: http://www.cnblogs.com/zhuyp1015/
# LastChange: 2012-06-20 22:48:29
========================================================================*/
#include <iostream>
#include <cstdio>
#include <iterator>
using namespace std;

class Color
{
    friend int mColoring(int,int,int**);
private:
    bool OK(int);
    void Trace(int, Color &);
    int n;
    int m;
    int** a;
    int* x;
    long sum;
};

bool Color::OK(int k)
{
    for(int j = 1; j < k; j++)//注意这里！只用判断前面的结点
        if( (a[k][j] == 1) && (x[j] == x[k]) )    return false;
    return true;
}

void Color::Trace(int t,Color &z)
{
    //cout<<"current t: "<< t <<endl;
    if( t > n )
    {
        sum ++;
        copy(z.x+1, z.x + n + 1, ostream_iterator<int>(cout, " "));
        cout<<endl;
    }
    else{
        for(int i = 1; i<= m; i++)
        {
            x[t] = i;
            if( OK(t))    Trace(t+1,z);
            x[t] = 0;
        }
    }
}

int mColoring(int n,int m,int** a)
{
    Color z;
    z.n = n;
    z.m = m;
    z.a = a;
    z.sum = 0;
    Color &zz = z;
    int* p = new int[n+1];
    for(int i = 0; i <= n; i++)
        p[i] = 0;

    z.x = p;

    z.Trace(1,zz);
    
    delete []p;
    return z.sum;
}

int main()
{
    int nodeNum,colorNum;
    freopen("color_painting.txt","r",stdin);
    cin>>nodeNum>>colorNum;

    int** mm = new int*[nodeNum+1];
    for(int i = 1; i <= nodeNum; i++)
    {
        mm[i] = new int[nodeNum+1];
        for(int j = 1; j <= nodeNum; j++)
        {
            cin>>mm[i][j];
            //cout<<mm[i][j]<<"\t";
        }
        //cout<<endl;
    }
    cout<<"NUM: "<<nodeNum<<"\t"<<colorNum<<endl;
    cout<<"mColoring: "<<mColoring(nodeNum,colorNum,mm)<<endl;

    return 0;
}

运行结果：

附：（测试数据）

5 4
0 1 1 0 0
0 1 1 0 1
1 1 0 0 1
0 1 0 0 1
0 1 1 1 0