地图着色

Posted on | In |

地图染色问题可以根据四色定理来解决。所谓四色定理，就是指可以用不多于四种的颜色对地图着色，使相邻的行政区域不重色，因此我们可以用四色定理的结论，用回溯算法对一幅给定的地图染色。

算法的基本思想是：从第(1)号行政区域开始染色，每个区域逐次用颜色1#、2#、3#、4#进行试探，若当前所取的颜色与周围已染色的行政区域不重色，则用栈记下该区域的颜色序号，否则依次用下一颜色进行试探；若出现用1#到4#颜色均与相邻区域的颜色重色，则需退栈回溯，修改当前栈顶的颜色序号，再进行试探。直到所有行政区域都已分配合适的颜色。

递归求解；在前面的n-1个节点都合法的着色之后，开始对第n个节点着色。这时候枚举可用的m个颜色，通过和与它相邻的节点的颜色相比较，来判断这个颜色是否合法。找到一种颜色能使第n个节点合法着色即可完成中国地图着色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
#define MAX 100
vector<vector<int> >g;
int x[MAX];
int n,m,e;
bool ok(int t){
	//t节点邻接表中序号小于t的颜色是否有相同的 剪枝 
	for(int i=0;i<g[t].size();i++){
		if(x[g[t][i]]==x[t]&&g[t][i]<t)
		return false;
	}
	return true;
}
int sum=0;
void back(int t){
	if(t>n){
		sum++;
		cout<<"第"<<sum<<"种方案:"; 
		for(int i=1;i<=n;i++)
		cout<<x[i]<<" ";
		cout<<endl;
	}
	else{
    //!! 1->m 没有颜色的默认是x[] 值是0
		for(int j=1;j<=m;j++){
			x[t]=j;//t位置填充j 
			if(ok(t))
			{
			back(t+1);	
			}
		}
	}
}
int main(){

	cin>>n;
	cin>>m;
	cin>>e;
	int k1,k2;
	g=vector<vector<int> >(n+1);
	for(int i=0;i<e;i++){
		cin>>k1>>k2;
		g[k1].push_back(k2);
		g[k2].push_back(k1);
	}
	back(1);
	
	
	
	
	
}

参考博客
https://blog.csdn.net/tengweitw/article/details/17641017

http://blog.51cto.com/qmkkd/1767279

image