算法题解：图的着色问题（给定无向连通图的顶点数和边数计算图的色数）—JAVA回溯算法

图的着色问题（给定图的顶点数和边数计算需要的颜色数）

问题描述

给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使图G中每条边的两个顶点有不同的颜色？

问题分析

这个问题是图的m可着色判定问题。

若一个图最少需要m种颜色才能使图中每条边相连接的两个顶点着不同颜色，称这个数m为这个图的色数。

求一个图的色数m称为图的m可着色优化问题。

给定一个图以及m种颜色，请计算出涂色方案数。

算法实现

package com.bean.algorithm.graph;

import java.util.Scanner;
/*
 * 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。
 * 是否有一种着色法使图G中每条边的两个顶点有不同的颜色？
 * */
public class MGraphColoring {
	
	public static int N=100;
	
	public static void main(String[] args) {
		// 接收键盘输入数据
		Scanner in = new Scanner(System.in);
		// 定义一个二维数组，限定
		int[][] a = new int[N][N];
		// 定义一个一维数组
		int[] b = new int[N];
		System.out.println("请输入顶点的数目和边的数目（顶点数小于100个）");
		// n——顶点数；m——边数
		int n = in.nextInt();
		int m = in.nextInt();
		System.out.println("边的连接");
		// 读取边的连接
		for (int i = 0; i < m; i++) {
			int x = in.nextInt();
			int y = in.nextInt();
			a[x][y] = 1;
			a[y][x] = 1;// 1代表连接
		}
		
		int t = n;
		// b[0]赋初值为100
		b[0] = 100;
		// 回溯算法
		trackback(a, b, m, n, t);//
		// 输出图的色数
		System.out.println(b[0]);

	}

	/*
	 * 算法设计
	 * 输入参数包括：图的邻接矩阵表示
	 * */
	private static void trackback(int[][] a, int[] b, int m, int n, int t) {
		int tmp = n;
		int state = 0, i, j;
		if (tmp <= 0) {
			int temp = b[1];
			for (int r = 1; r <= t; r++) {
				if (temp < b[r])
					temp = b[r];

			}
			if (temp < b[0])// b[0]代表最小的颜色,temp代表此次的颜色种数
				b[0] = temp;
			return;
		}
		for (i = 1; i <= t; i++)// 颜色
		{
			state = 0;
			b[tmp] = i;
			for (j = 1; j <= t; j++)// 边的连接
			{

				if (a[tmp][j] == 1 && b[j] != b[tmp]) {
					continue;// trackback(a,b,m,n-1,t);
				} else if (b[j] == b[tmp] && a[tmp][j] == 1) {
					if (j == tmp)// 如果是本身与自身的连接那么不管
						continue;
					state = 1;
					break;
				}
			}
			if (state != 1) {

				trackback(a, b, m, n - 1, t);
			}
		}

	}

}

程序运行结果：

请输入顶点的数目和边的数目（顶点数小于100个）
（输入）5 6
边的连接（输入值）
0 1
0 2
1 2
1 3
2 3
3 4
图的色数为：3