图m着色问题
图m着色问题
用户1154259
发布于 2018-01-17 16:07:21
发布于 2018-01-17 16:07:21
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 <iostream>
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<<x[i]<<" ";
cout<<endl;
}
else
{
for(int i=1;i<=m;i++)
x[t] = i;
if(Ok(t))
Backtrack(t+1);
x[t] = 0;
}
}
int mColoring(int n,int m,int * * a)
{
Color X;
X.n = n;
X.m = m;
X.a = a;
X.sum = 0;
int * p = new int [n+1];
for(int i=0;i<=n;i++)
p[i] = 0;
X.x = p;
X.Backtrack(2);
delete [] p;
return X.sum;
}
int main()
{
int n,m;
cout<<"请输入想要确定的m着色图中m的值："<<endl;
cin>>m;
cout<<endl<<"共有n个结点，n的值为："<<endl;
cin>>n;
int **arr = new int [n][n];
for(int i=0;i<n;i++)
{
cout<<"请输入连接矩阵的第一行的数（0-1）"<<endl;
for(int j=0;j<n;j++)
{
cin>>arr[i][j];
}
}
mColoring(n,m,arr);
return 0;
}运行结果：
--------------------Configuration: test102501 - Win32 Debug--------------------
Compiling...
test.cpp
E:\study file\ACM\test102501\test.cpp(63) : error C2540: non-constant expression as array bound
E:\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 cast
Error executing cl.exe.
test.obj - 2 error(s), 0 warning(s)还是不会指针数组的传参...有空看看，mark一下
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2012-10-25 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读