图的着色问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了图的着色问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

问题1：
图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？
但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。
输入格式：
输入在第一行给出3个整数V（0<V≤500）、E（≥0）和K（0<K≤V），分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数N（≤20），是待检查的颜色分配方案的个数。随后N行，每行顺次给出V个顶点的颜色（第i个数字表示第i个顶点的颜色），数字间以空格分隔。题目保证给定的无向图是合法的（即不存在自回路和重边）。
输出格式：
对每种颜色分配方案，如果是图着色问题的一个解则输出Yes，否则输出No，每句占一行。

问题2：
给定无向连通图和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的两个顶点有不同的颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边相连接的两个顶点着不同颜色，称这个数m为这个图的色数。求一个图的色数m称为图的m可着色优化问题。给定一个图以及m种颜色，请计算出涂色方案数

问题3：
基于问题2，对问题2进行拓展，输出最少需要的颜色数量;
问题4：
利用回溯法，对给定无向图进行染色;文章来源地址https://www.toymoban.com/news/detail-418804.html

问题1 的实现代码：

#include<iostream>
#include<cstring>
#include <set>
#include <map>
#include <ctime>
#include <bitset>
#include <sstream>
#include <algorithm>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>//getch()的头文件
#include<vector>
#include<queue>
#include<stack>
using namespace std;
//
const int N=510;//二维数组的最大行列数 
int v,e,k,col[N],vis[N],g[N][N];//v为顶点数，e为边数，k为颜色数 
bool dfs(int u ){
   //从某个顶点开始，进行深搜 
	for(int i =1;i<=v;i++){
   //这里每一个顶点都是有顺序的，是递增的 
		if(!vis[i]&&g[u][i]==1){
   //如果没有访问过，而且顶点间是有边的 
			vis[i]=true;//因为是无向图，因此有环，为避免一直递归，应该加一个访问位vis (true==1) 
			if(col[u]==col[i]) return false;//如果两个点的颜色是相同的，直接返回false 
			else return dfs(i);
		} 
	}
	return true;//如果循环遍历完所有的顶点都没有相邻颜色相同的则返回true 
}
int main()
{
   
	memset(g,0x3f,sizeof g);//对数组进行初始化 
	scanf("%d %d %d",&v,&e,&k);//输入顶点数v,边数e,颜色数k 
	for(int i =0;i<e;i++){
   
		int a,b;//a,b都当作是一个顶点了;此代码中N=510,则就有510x510条无向边的可能 
		scanf("%d %d",&a,&b);//输入哪两个顶点,两个顶点的值都设置为1,不过在二位数组中，其图的实际的相对位置并没有体现出来，而是以逻辑关系体现出来的
		//比如无向边 (1,2),和(1,3),其逻辑意义是,它们的交界点是1,也就是顶点1,因此呢，我们的顶点，是可以用一个一维数组来体现的。 
		 
		g[a][b]=g[b][a]=1;//无向边,因此需要两个方向都赋值为1; 
	}
	int n;//这个是输入判断情况的个数 
	scanf("%d",&n);
	for(int i =1;i<=n;i++){
   
		set<int> s;//set的数据唯一，而且自动排序 
		for(int j=1,c;j<=v;j++){
   //从顶点1开始，分别读取各个顶点的颜色 
			scanf("%d",&c);//读取颜色记录在c中 
			col[j]=c;//将c赋值给col数组,值得注意的是，这个数组的每一个下标都是一个顶点 
			s.insert(c)