图的m着色问题

/*  Name: 图的m着色问题  Copyright:   Author: 巧若拙   Date: 07-03-17 08:21  Description:   问题描述：给定无向连通图 G 和 m 种不同的颜色。用这些颜色为图 G 和各顶点着色，每个顶点着一种颜色。是否有一种着色法使得图 G 中每条边的两个顶点着不同的颜色。这个问题是图的 m 可着色判定问题。若一个图最少需要 m 种颜色才能使图中的每条边连接的两个顶点着不同的颜色，则称这个数 m 为该图的色数。求一个图的色数 m 的问题称为图的 m 可着色优化问题。子集树，O(n*(m^n))时间复杂度四色问题是m图着色问题的一个特例，根据四色原理，证明平面或球面上的任何地图的所有区域都至多可用四种、颜色来着色，并使任何两个有一段公共边界的相邻区域没有相同的颜色。这个问题可转换成对一平面图的４－着色判定问题(平面图是一个能画于平面上而边无任何交叉的图)。将地图的每个区域变成一个结点，若两个区域相邻，则相应的结点用一条边连接起来。多年来，虽然已证明用5种颜色足以对任一幅地图着色，但是一直找不到一定要求多于4种颜色的地图。直到1976年这个问题才由爱普尔，黑肯和考西利用电子计算机的帮助得以解决。他们证明了4种颜色足以对任何地图着色。在这一节，不是只考虑那些由地图产生出来的图，而是所有的图。讨论在至多使用m种颜色的情况下，可对一给定的图着色的所有不同方法。 分析：可以通过回溯的方法，不断的为每一个节点着色，在前面n-1个节点都合法的着色之后，开始对第n个节点进行着色，这时候枚举可用的m个颜色，通过和第n个节点相邻的节点的颜色，来判断这个颜色是否合法，如果找到那么一种颜色使得第n个节点能够着色，那么说明m种颜色的方案是可行的。*/#include<iostream>#include<string>using namespace std;const int N = 5; //图中节点的个数const int m = 3; //颜色的种int map[N][N]={0,1,1,0,1,               1,0,1,1,0,               1,1,0,1,1,               0,1,1,0,1,               1,0,1,1,0};//邻接矩阵int c[N];//记录着的是哪种颜色int sum = 0;//保存可以着色的方案数bool OK(int t);//检查当前顶点着色是否合法 void Backtrace(int t); //递归回溯 void Backtrace_2(); //非递归回溯 int main() {   Backtrace(0);  // Backtrace_2();      system("pause");   return 0;}bool OK(int t)//检查当前顶点着色是否合法 {    for(int i=0; i<t; i++)    {        if(map[i][t] == 1 && c[i] == c[t])      			return false;           }    return true;}void Backtrace(int t) //递归回溯 {    if(t == N)    {        sum++;        cout << "方案" << sum << ": ";        for(int i=0; i<N; i++)        {            cout << c[i] << " ";        }        cout << endl;    }    else    {        for(int i=1; i<=m; i++)        {			c[t] = i;            if(OK(t))				Backtrace(t+1);        }      //  c[t] = 0;   //颜色还原并回溯（由于c[t]每次都从1开始取值，故颜色无需还原）     }}void Backtrace_2() //非递归回溯 {	int t = 0; //第一个顶点入栈		while(t >= 0)	{		while(c[t]++ < m)//c[t]默认初始化为0 		{			if (OK(t)) //c[t]颜色可行才进入下一步 			{				if(t == N-1)				{					sum++;					cout << "方案" << sum << ": ";					for(int i=0; i<N; i++)					{						cout << c[i] << " ";					}					cout << endl;				}				else				{					t++;				}			}		}		c[t--] = 0; //颜色还原并回溯	}}