转自

 

图的m-着色判定问题——给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色?

图的m-着色优化问题——若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的最小色数m的问题称为m-着色优化问题。

 

算法描述（迭代算法）

 

 color[n]存储n个顶点的着色方案，可以选择的颜色为1到m

t=1->n

对当前第t个顶点开始着色：

 　if: 　　t>n  则已求得一个解，输出着色方案即可

else: 　　依次对顶点t着色1-m，

   　　　  　　if: 　　t与所有其它相邻顶点无颜色冲突，则继续为下一顶点着色；

　　　　　 else:  　  回溯，测试下一颜色。

 

///图着色问题回溯法/**无向图邻接矩阵示例1 1 0 0 01 1 0 1 01 0 0 1 01 0 0 1 01 1 1 0 0*/#include "cstdio"#include "cstring"int color[500];bool ok(int k,int c[][100]){    for(int i=1;i
     
      =1)    {        color[k]+=1;///染第一种颜色        while(color[k]<=m)        {            if(ok(k,c))                break;            else                color[k]++;///搜索下一个颜色        }///挑选合适颜色        if(color[k]<=m&&k==n)///找完  输出        {            for(int i=1;i<=n;i++)                printf("%d ",color[i]);            printf("\n");            cnt++;        }        else if(color[k]<=m&&k
     

 

每一个程序，都在讲着自己的故事

写程序 讲故事