回溯法解m着色问题.cpp

算法分析中

/*
问题描述：
给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点
着一种颜色。试问是否有使得G中任何一条边的2个顶点着有不同颜色的着色法。这个问题
就是一个图的m可着色判定问题。若一个图最少需要m种颜色才能使图中任何一条边连接的
2个顶点着有不同颜色，则称这个数m为该图的着色数。
*/
/*
算法设计：
图的邻接矩阵表示图a表示一个无向连通图G=(V,E)。若(i,j)属于图G=(V,E)
的边集E,则a[i][j] = 1,否则a[i][j] = 0。用整数1,2,...,m来表示m种不同的颜色。
顶点i所着的颜色用x[i]来表示。因此，该问题的解向量可以表示为n元组x[1:n]。问题
的解空间为一棵高度为n+1的完全m叉树。解空间树的第i(1<=i<=n)层中每一个结点都有
m个儿子，每个儿子相应于x[i]的m个可能的着色之一。第n+1层结点均为叶结点。
*/
/*
在函数Backtrack中，当i>n时，表示算法已搜索至一个叶结点，得到一个新的m着色
方案，因此当前已找到的可m着色方案数sum增1。
当i<=n时，当前扩展结点Z是解空间中的一个内部结点。该结点有x[i] = 1,2,...,m共有
m个儿子结点。对当前扩展结点Z的每一个儿子结点，由函数OK检查其可行性，并以深度
优先的方式递归地对可行子树进行搜索，或剪去不可行的子树
*/
#include<iostream>
using namespace std;

class Color
{
	friend int mColoring(int,int,int**);
private:
	bool Ok(int k);
	void Backtrack(int t);
	int n;
	//图的顶点数
	int m;
	//可用的颜色数
	int **a;
	//图的邻接矩阵
	int *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] ) )
		//只要当前点着色与任何一个相邻点颜色相同就返回false
		{
			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;
			//着颜色i
			if ( Ok(t) )
			{
				//如果和相邻点没有冲突就开始下一个点
				Backtrack(t+1);
			}
		}
	}
}

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;
	}
	X.x = p;
	X.Backtrack(1);
	delete []p;
	return X.sum;
}

/*
算法效率：
解空间树中内结点个数是m^i之和(0<=i<=n-1)。对每一个结点，最坏情况下
，函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性需耗时O(mn)。
因此回溯法总的时间消耗为O(nm^n)
*/
int main()
{
	int **p;

	return 0;
}