算法分析 | 回溯法 | 地图着色

一.问题分析

地图着色问题是01背包问题的推广,可以抽象看作无向连通图

由0/1两种状态变成了{1,2,3....N} 这N种状态,逻辑结构也从二叉树->N叉树.

这时就不能像之前那样:左子树写一段代码,右子树写一段代码.

用for()遍历每一个状态并递归,而且因为没有"不涂色",也就是说没有0状态,所以也不存在限界条件

二.代码分析

分为4部分

1.全局变量定义

2.约束函数

3.初始化函数

4.递归函数

1.定义全局变量

const int M3 = 21;
int map[M3][M3];		//记录结点的连接状况,1表示连接,0表示未连接
int n3;				//表示n个结点
int e;	                	//表示有e条边

int color_num;			//用户输入颜色数量,小于M3
int color[M3];			//color[1]=2表示结点1的颜色是2
int countg = 0;		        //记录最优解

2.约束函数

约束函数的功能:

如果 目前元素 t 与元素 0 ~ t-1 中,有相邻并且颜色一样的,返回false

bool place3(int t)		//t表示当前结点的序号
{
	bool flag = true;
	for (int i = 1; i < t; i++)	//检查当前结点和之前的全部结点 是否相邻并且同色
	{
		if (map[t][i] && color[t] == color[i])
		{
			flag = false;
			break;
		}
	}
	return flag;
}

3.初始化函数

用户自定义元素个数(int)、联通情况(int[ ][ ])、颜色数量(int)

void creategraph()
{
	cout << "请输入1~20以内的数作为图的结点个数：";
	cin >> n3;
	if (n3 > 20)
	{
		cout << "输入值偏大，请重新输入：";
		cin >> n3;
	}
	cout << "请输入颜色的个数：";
	cin >> color_num;
	if (n3 < 2)
	{
		cout << "不可能有此输入值，请重新输入：";
		cin >> color_num;
	}

	int u, v;
	cout << "输入边数	"; cin >> e; cout << endl;
	cout << "输入结点1~结点20中,有边连接的点u和v
";
	for (int i = 0; i < e; i++)
	{
		cout << "输入第"<<i+1<<"条边的端点1:		";
		cin >> u; cout << endl;
		cout << "输入第" << i + 1 << "条边的端点2:		";
		cin >> v; cout << endl;
		map[u][v] = 1;
		map[v][u] = 1;
	}
}

4.递归函数

void GraphColor(int t)//i表示图里有i个结点
{
	//先写终止条件 
	if (t>n3)		//此时已递归完所有结点 (这里的元素是从1开始的,所以不是">=")
	{
		countg++;		//解的数量多了一种
		for (int i = 1; i <= n3; i++)
		{ 
			cout << color[i] << "	";
		}
		cout << endl;
	}
	else
	{
		for (int i = 1; i <= color_num; i++)
		{
			color[t] = i;
			
			if (place3(t))
			{
				GraphColor(t + 1);
			}
		}
	}
	
}