#include<iostream>
class Color
{
friend int mColoring(int,int,int **);
private:
bool OK(int k);
void Backtrack(int t);
int n;// 图的顶点数
int m;// 可用颜色数
int **a;// 图的邻接矩阵
int *x;// 当前的解
long sum;// 当前找到 m种颜色的着色方案数
public:
Color();
virtual ~Color();
};
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++;
if(sum==1)
{
for(int i=1;i<=n;i++)
{
switch(x[i])
{
case 1:cout<<" 第"<<i<<" 区域着红色 "<<endl;
break;
case 2:cout<<" 第"<<i<<" 区域着蓝色 "<<endl;
break;
case 3:cout<<" 第"<<i<<" 区域着绿色 "<<endl;
break;
case 4:cout<<" 第"<<i<<" 区域着黄色 "<<endl;
break;
}
}
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
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(1);
delete []p;
return X.sum;
}
#include<iostream>
#include"olor.h"
using namespace std;
int main()
{
int **a;
int i,j,b,c;
cout<<" 请输入邻接矩阵维数 :"<<endl;
cin>>b;
cout<<endl;
cout<<" 请输入使用颜色数目 :"<<endl;
cin>>c;
cout<<endl;
a=new int *[b+1];
for(i=1;i<=b;i++)
a[i]=new int[b];
cout<<" 请输入邻接矩阵数据 :"<<endl;
for(i=1;i<=b;i++)
{
for(j=1;j<=b;j++)
{
cin>>a[i][j];
}
}
cout<<" 输入邻接矩阵的数据如下 :"<<endl;
for(i=1;i<=b;i++)
{
for(j=1;j<=b;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
cout<<"Test:"<<endl;
int temp=mColoring(b,c,a);
cout<<" 其中不同的配色方案总共有 "<<temp<<"种"<<endl;
delete []a;
cout<<" 四色定理 : 任何一张地图只用四种颜色就能使具有共同边界的国家
着上不同的颜色 ."<<endl;
system("pause");
return 0;
}
class Color
{
friend int mColoring(int,int,int **);
private:
bool OK(int k);
void Backtrack(int t);
int n;// 图的顶点数
int m;// 可用颜色数
int **a;// 图的邻接矩阵
int *x;// 当前的解
long sum;// 当前找到 m种颜色的着色方案数
public:
Color();
virtual ~Color();
};
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++;
if(sum==1)
{
for(int i=1;i<=n;i++)
{
switch(x[i])
{
case 1:cout<<" 第"<<i<<" 区域着红色 "<<endl;
break;
case 2:cout<<" 第"<<i<<" 区域着蓝色 "<<endl;
break;
case 3:cout<<" 第"<<i<<" 区域着绿色 "<<endl;
break;
case 4:cout<<" 第"<<i<<" 区域着黄色 "<<endl;
break;
}
}
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
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(1);
delete []p;
return X.sum;
}
#include<iostream>
#include"olor.h"
using namespace std;
int main()
{
int **a;
int i,j,b,c;
cout<<" 请输入邻接矩阵维数 :"<<endl;
cin>>b;
cout<<endl;
cout<<" 请输入使用颜色数目 :"<<endl;
cin>>c;
cout<<endl;
a=new int *[b+1];
for(i=1;i<=b;i++)
a[i]=new int[b];
cout<<" 请输入邻接矩阵数据 :"<<endl;
for(i=1;i<=b;i++)
{
for(j=1;j<=b;j++)
{
cin>>a[i][j];
}
}
cout<<" 输入邻接矩阵的数据如下 :"<<endl;
for(i=1;i<=b;i++)
{
for(j=1;j<=b;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
cout<<"Test:"<<endl;
int temp=mColoring(b,c,a);
cout<<" 其中不同的配色方案总共有 "<<temp<<"种"<<endl;
delete []a;
cout<<" 四色定理 : 任何一张地图只用四种颜色就能使具有共同边界的国家
着上不同的颜色 ."<<endl;
system("pause");
return 0;
}