算法题解：对于给定的无向连通图G和m种不同的颜色计算图的所有不同着色法（JAVA代码）

对于给定的无向连通图G和m种不同的颜色计算图的所有不同着色法

问题描述

 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。

如果有一种着色法使图G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。

图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。

你的任务是对于给定的无向连通图G和m种不同的颜色，编写一个JAVA程序来计算无向图G的所有不同着色法。

输入数据格式为：

第一行输入无向图的顶点数 v ，边数 e 和可用的颜色数 cm

第二行开始至第 e 行输入两个顶点连接的边（u，v），u和v输入时以空格区分。

输入样例数据：

5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
输出结果：
48
 

算法实现

package com.bean.algorithm.graph;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/*
 * 【问题描述】
 * 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。
 * 如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。
 * 图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。
 * 【任务】
 * 对于给定的无向连通图G和m种不同的颜色，编程计算图的所有不同的着色法。
 * 【输入格式】
 * 第1行有3个正整数n，k 和m，表示给定的图G有n个顶点和k条边，m种颜色。
 * 顶点编号为1，2，…，n。
 * 接下来的k行中，每行有2个正整数u,v，表示图G 的一条边(u,v)。
 * 【输出格式】
 * 程序运行结束时，将计算出的不同的着色方案数输出。
 * 【输入样例】
 * 5 8 4
 * 1 2
 * 1 3
 * 1 4
 * 2 3
 * 2 4
 * 2 5
 * 3 4
 * 4 5
 * 【输出样例】
 * 48
 * */
public class NumberofColoring4 {
	//定义一个Set
	public static Set<String> set = new HashSet<String>();
	public static int v = 0;// 顶点数
	public static int e = 0;// 边数
	public static int cm = 0;// 颜色数
	public static int a = 0;// 边的连接起点
	public static int b = 0;// 边的连接终点
	public static int count = 0;// 方案数
	public static int[][] num;// 二维数组表示边的连接矩阵（邻接表）
	public static int[] color;//
	public static boolean[] flag;//

	public static void main(String[] args) {
		//接收键盘输入
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入顶点数（v），边数（e），色数（cm）:");
		v = sc.nextInt();//顶点数
		e = sc.nextInt();//边数
		cm = sc.nextInt();//颜色数
		//开辟一个二维数组，用于形成顶点的邻接表（邻接矩阵）
		num = new int[v + 1][v + 1];
		//开辟一个一维数组
		color = new int[v + 1];
		//开辟一个一维数组
		flag = new boolean[cm + 1];
		//接收边的输入值
		for (int i = 0; i < e; i++) {
			a = sc.nextInt();
			b = sc.nextInt();
			//边的连接
			num[a][b] = 1; 
			num[b][a] = 1;
		}
		//回溯算法
		backtrack(1, "");
		//输出着色的方案数
		System.out.println(count);

	}

	/*
	 * 设计回溯算法
	 * 输入参数 vertex: 代表搜索的顶点
	 * 输入参数 s: 
	 * */
	public static void backtrack(int vertex, String s) {
		if (vertex == v + 1) {
			set.add(s);
			count++;
			return;
		}
		for (int i = 1; i <= cm; i++) {

			int tmp = 0;
			for (int j = 1; j <= v; j++) {
				if (num[vertex][j] == 1 && i == color[j]) {
					tmp = 1;
					break;
				}
			}
			if (tmp == 0) {
				flag[i] = true;
				color[vertex] = i;
				//回溯
				backtrack(vertex + 1, s + i);
				color[vertex] = 0;
				flag[i] = false;
			}
		}

	}
}

程序运行结果：

48