回溯方法解图着色问题

   给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题.

   cu贴图真是不方便,就不搞图了!!!问题描述大家search下到处都是!!!!这个与n queen一样典型的回溯方法....

  add_color(int A[7][7], int color[7], int start,int m)，我这里图就偷懒用的是矩阵表示方法.... color表示7个节点的颜色...start表示已经处理到第几个节点了...m是总的颜色数目....其实m可以定义为一个global var

#include <stdio.h>
#include <stdlib.h>

void print_array(int dist[], int n)
{
  int i;
  printf("begin\n");
  for(i=0;i<n;i++)
   {
     printf("%d color %d\n", i+1, dist[i]);
   }
  
  printf("end\n");
}

int conflict(int A[7][7], int color[7], int start)
{
  int i;
  for(i=0;i<start;i++)
   {
    if((A[i][start]!=0)&&color[i]==color[start])
      return 1;
   }
   
   return 0;
}

void add_color(int A[7][7], int color[7], int start,int m)
{
 int i;
 if(start>=7)
  {
    print_array(color, 7);
    system("PAUSE");
    return;
  }
 for(i=1;i<=m;i++)
  {
    color[start] = i;
    if(conflict(A, color, start)==0)
      add_color(A, color, start+1, m);
  }
}

int main(int argc, char *argv[])
{
  int A[7][7] = {
                  {0,1,1,1,0,0,0},
                  {1,0,0,0,1,0,0},
                  {1,0,0,1,0,1,0},
                  {1,0,1,0,1,1,1},
                  {0,1,0,1,0,0,1},
                  {0,0,1,1,0,0,1},
                  {0,0,0,1,1,1,0}
                 };
  int color[7];
  
  add_color(A, color, 0, 3);
  system("PAUSE");    
  return 0;
}


 

 我先自己以为m是4,填了个4机器算了好久,出来N屏幕的数据^_^.看来电脑比我聪明...M为3就可以了...

 

add_color(start)
{
 if(满足了)
   输出

 for(n种可能)
  {
   color[start]=其中的一种可能
   if(conflict(...color, start)==0)
    {
     add_color(.. start+1...)
    }
  }
}
上面就是典型的回溯的过程了,有兴趣可以去看看我那个n_queen。。流程也是这么个样子.