回溯算法的基本特征：首先节点是用深度优先搜索的方法生成的；第二，不需要存储整颗搜索树，我们只需要存储根到当前活动节点的路径。事实上，根本没有生成有形的节点，整棵树都是隐含的。

#includeusing namespace std;
int Adjacent[5][5]=
{{0,1,1,0,0},
{1,0,0,1,1},
{1,0,0,1,1},
{0,1,1,0,1},
{0,1,1,1,0}};//邻接矩阵
int c[5];//全局变量,默认初始化为0
int k;//全局变量
int IsLegal()//判断两个点是否邻接，并且着的颜色是否一样
{
 for(int i=0;i<=k;i++)
  for(int j=0;j=0)  //实现回溯的过程
 {
  while(c[k]<=2)//控制颜色的选择
  {
   c[k]++;//选择另外一种颜色
  if(!IsLegal())//如果选择的点不合法，则进行下此循环,选择另外一种颜色
   continue;
  if(k==4)//如果所有的点都着了颜色，则输出
  {
  for(int i=0;i<=4;i++)
             cout<<c[i]<<" ";
   cout<<endl;
  }
  else
   k++; //前进选择下一个结点
  }
  c[k]=0;
  k--;//回溯
 }
}

int main(int argc, char* argv[])
{
 ColorIter();
 return 0;
}

>

赞0 2363次