算法与数据结构——图的着色问题（图论、着色问题、深度优先搜索） -- 酱懵静

图的着色问题

问题描述
存在一个无向图，要求给图中的点涂色，并且有线连接的点之间不能是同一种颜色

输入格式
第一行为两个正整数n,m( 0<n,m<100 )，分别表示录入的图的点数以及边数
第二行为一个正整数num，表示能用的颜色数（每种颜色用一个正整数来表示，从1开始逐渐增1的正整数）
之后为m行，每行两个数x,y，表示点x和y之间有一条边（点从1开始，为逐渐增1的正整数）

输出格式
按照点的顺序，输出所有点的着色方案，格式见样例输出（中间为’ \t’，空格+制表位）

样例输入1：
3 3
3
1 2
1 3
2 3

样例输出1：
point:1 color:1
point:2 color:2
point:3 color:3

point:1 color:1
point:2 color:3
point:3 color:2

point:1 color:2
point:2 color:1
point:3 color:3

point:1 color:2
point:2 color:3
point:3 color:1

point:1 color:3
point:2 color:1
point:3 color:2

point:1 color:3
point:2 color:2
point:3 color:1

样例输入2：
3 2
2
1 2
1 3

样例输出2：
point:1 color:1
point:2 color:2
point:3 color:2

point:1 color:2
point:2 color:1
point:3 color:1

---

---分割线---

---

对题目的简化解读：存在一个无向图，要求给图中的点涂色，并且有线连接的点之间不能是同一种颜色

分析：
深度优先搜索+回溯
着色问题，我们的解决思路应该从搜索出发。如果使用贪心，把互不连接的用同一颜色表示，是很难枚举完所有情况的的，并且难以保证每种情况间的唯一性。而使用搜索的思想，则可以避免这一问题。

我们从第一个点出发，不断地走进下一个点并且着色（需保证这种情况下着色的可行性），当走到最后一个点时（即当前点的序号大于了点的总数时）即是找到了一种着色方案。这时候，我们输出这个具体的着色方案，然后回溯。这里的回退是回退到当前涂某种颜色那个地方（即前一次调用dfs函数的那个循环那里）。于是在这不断地dfs下，其又将尝试对于当前点而言的其他着色方案并不断发散。
这样就保证了能把所有的着色方案都枚举到，并且彼此之间唯一。

本题实则是为蓝桥杯 历届试题 分考场这道题做预热~~~~~

---

---分割线---

---

下面给出本题完整代码：

#include<iostream>
using namespace std;

const int MAX=105;			//定义最大的顶点数
int n,m,num;				//分别代表点数、边数和可用颜色数
int map[MAX][MAX];			//对于小规模的数量可以直接使用邻接矩阵（也可以用向量，但没必要）
int color[MAX]; 			//color[i]=x表示第i个点涂上代号为x的颜色

bool judge(int pos,int col) //检测在当前pos位上涂上颜色代号为col的方案是否可行
{
	for(int i=1;i<=n;i++)
		if(map[pos][i] && color[i]==col) return false;
	return true; 
}
void dfs(int pos)
{
	if(pos>n)
	{
		for(int i=1;i<=n;i++)
			cout<<"point:"<<i<<" \tcolor:"<<color[i]<<endl;
		cout<<endl;
		return;
	}
	for(int i=1;i<=num;i++)
	{
		if(judge(pos,i))
		{
			color[pos]=i;
			dfs(pos+1);
			color[pos]=0;	//回退时必须把刚才点的着色去掉，否则会影响回退之后的dfs 
		}
	}
}
int main()
{
	int x,y; 
	cin>>n>>m>>num;
	for(int i=0;i<m;i++)
	{
		cin>>x>>y;
		map[x][y]=map[y][x]=1;
	}
	dfs(1); 
	return 0;
}