图m着色问题-白红宇

1 问题描述：

　　给定无向图，m种不同的颜色。使每一种着色法使G中每条边的2个顶点不同颜色，若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则成这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

2 算法设计

　　用图的邻接矩阵a表示无向图连通图G=（V,E）。

　　若存在相连的边，则a[i][j] = 1，否则 a[i][j]=0.

　　整数1,2,3.。。m用来表示为一棵高度为n+1的完全m叉树。

　　解空间树的第i层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一。

　　第n+1层为叶子结点。

在算法Backtrack,

　　当i>n时，算法搜索至叶节点，得到新的m着色方案，当前找到可m着色的方案树增1.

　　当i<=n时，当前扩展结点Z是解空间中的内部结点。该结点有x[i]=1,2,3.。。m共m个儿子结点。对当前扩展结点Z的每一个儿子结点，由函数OK检查其可行性，并以深度优先的方式递归地对可行子树搜索，或剪去不可行子树。

算法描述：

#include 
      
       using namespace std;class Color{    friend int mColoring(int,int,int* *);private:    bool Ok(int k);    void Backtrack(int t);    int n,        m,        * *a,        * x;    long sum;};bool Color::Ok(int k){    for(int j=1;j<=n;j++)        if((a[k][j] == 1)&&(x[j] == x[k]))            return false;    return true;}void Color::Backtrack(int t){    if(t>n)    {        sum++;        for(int i=1;i<=n;i++)            cout<
       
        <<" ";        cout<
        
         >m;    cout<
         
          <<"共有n个结点，n的值为："<
          
           >n;    int **arr = new int [n][n];    for(int i=0;i
           
            >arr[i][j]; } } mColoring(n,m,arr); return 0;}

运行结果：

--------------------Configuration: test102501 - Win32 Debug--------------------Compiling...test.cppE:\study file\ACM\test102501\test.cpp(63) : error C2540: non-constant expression as array boundE:\study file\ACM\test102501\test.cpp(63) : error C2440: 'initializing' : cannot convert from 'int (*)[1]' to 'int ** '        Types pointed to are unrelated; conversion requires reinterpret_cast, C-style cast or function-style castError executing cl.exe.test.obj - 2 error(s), 0 warning(s)

还是不会指针数组的传参...有空看看，mark一下

本文转自博客园xingoo的博客，原文链接：，如需转载请自行联系原博主。