数据结构C语言 四染色定理

来源：百度知道 编辑：UC知道 时间：2024/06/17 19:02:10
地图四染色问题~

是地图上相邻板块不重色，最少用四种颜色对地图着色，证明此定理得结论，利用栈采用回溯法对地图着色

细想： 对每个行政区编号：1-7
对颜色编号： a、b、c、d；
从第一号行政区开始逐一染色，每个区域逐次用四种颜色进行试探，若所取颜色与周围不重，则用栈记下来该区得色数，否则一次用下一色数进行试探。若出现a-d均与周围发生重色，则需退栈回溯，修改当前栈顶得色数。
那个是思想 不是 细想 打错了

下面是用的c++描述的：涉及到类的有关知识。你不知道的话我可以帮你改为c语言描述。不过需要时间（这个星期之内），我最近比较的忙。反正你加了分，你就慢慢等吧！不好意思，我最近太忙了，没时间给你改。再加点分让别人给你回复吧！
class color{
friend int mcoloring(int,int,int * *);
private:
bool OK(int k);
void Backtrack(int t）；
int n,//图的定点数
m,//可用颜色数
**a,//图的临接矩阵
*x;//当前解
long sum;//当前已找到的可m着色方案数
};
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))Backtrck(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;