JAVA算法：无向图的着色（Graph Coloring）问题

图着色（Graph Coloring）问题

图着色问题（Graph Coloring Problem, GCP） 又称着色问题，是最著名的NP—完全问题之一。道路着色问题（Road Coloring Problem）是图论中最著名的猜想之一。

数学定义：给定一个无向图 G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的K值。

图的m—着色判定问题

给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色?

图的m—着色优化问题

若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的最小色数m的问题称为m—着色优化问题。
 

基本贪心着色算法

1. 第一步：用第一种颜色给第一个顶点着色。
2. 第二步：对剩余的 V-1 顶点执行以下操作：

• 考虑当前选取的顶点，并用以前从未使用过的最低编号的颜色为相邻的顶点着色。
• 如果所有以前使用的颜色都出现在于 v 相邻的顶点上，则为其指定新颜色。

算法实现

package com.bean.algorithm.graph;import java.util.Arrays;
import java.util.Iterator;
import java.util.Li