首页 > 代码库 > 图m着色问题
图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 <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一下
图m着色问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。