图着色问题是图论中最经典的NP完全问题之一，在课程表编排、寄存器分配、地图着色、频谱分配等领域有广泛应用。本文用Java实现Welsh-Powell贪心着色算法，并结合DSatur改进策略，深入讲解图着色的核心思想与实现细节。
一、问题定义
给定无向图G=(V,E)，图着色是指为每个顶点分配一种颜色，使得任意相邻的两个顶点颜色不同。色数χ(G)是完成合法着色所需的最少颜色数。确定色数是NP完全问题。
1.1 相关概念
- 色数（Chromatic Number）：图G正常着色所需的最少颜色数
- 色多项式：用k种颜色着色图G的方案数
- Welsh-Powell算法：按度数降序排列顶点，依次选择最小可用颜色
- DSatur算法：每次选择饱和度（已着色邻居的不同颜色数）最高的顶点
二、算法原理
2.1 Welsh-Powell算法
- 将所有顶点按度数从大到小排序
- 依次为每个顶点分配最小的可用颜色
- 返回使用的颜色总数
该算法是贪心策略，虽然不能保证最优解，但通常能得到较好的近似结果。
2.2 DSatur算法（改进版）
- 选择度数最大的顶点作为起始，赋予颜色1
- 在剩余未着色顶点中，选择饱和度最高的顶点
- 饱和度相同时，选择度数最大的顶点
- 为该顶点分配最小可用颜色
- 重复步骤2-4直到所有顶点着色
DSatur通常比Welsh-Powell获得更少的颜色数。
三、Java实现
import java.util.*;
/**
* 图着色问题求解
* 实现Welsh-Powell算法和DSatur算法
*/
public class GraphColoring {
private final int vertices;
private final List<Set<Integer>> adjacencyList;
public GraphColoring(int vertices) {
this.vertices = vertices;
this.adjacencyList = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
adjacencyList.add(new HashSet<>());
}
}
/**
* 添加无向边
*/
public void addEdge(int u, int v) {
adjacencyList.get(u).add(v);
adjacencyList.get(v).add(u);
}
/**
* 获取顶点度数
*/
public int degree(int v) {
return adjacencyList.get(v).size();
}
/**
* Welsh-Powell贪心着色算法
* 按度数降序排列，依次分配最小可用颜色
* @return 每个顶点的颜色数组（颜色从0开始编号）
*/
public int[] welshPowellColoring() {
int[] colors = new int[vertices];
Arrays.fill(colors, -1); // -1表示未着色
// 按度数降序排列顶点
Integer[] vertexOrder = new Integer[vertices];
for (int i = 0; i < vertices; i++) {
vertexOrder[i] = i;
}
Arrays.sort(vertexOrder, (a, b) -> degree(b) - degree(a));
int maxColor = -1;
for (int v : vertexOrder) {
// 收集邻居已使用的颜色
boolean[] usedColors = new boolean[vertices];
for (int neighbor : adjacencyList.get(v)) {
if (colors[neighbor] != -1) {
usedColors[colors[neighbor]] = true;
}
}
// 分配最小的可用颜色
for (int c = 0; c < vertices; c++) {
if (!usedColors[c]) {
colors[v] = c;
maxColor = Math.max(maxColor, c);
break;
}
}
}
return colors;
}
/**
* DSatur着色算法（改进的贪心算法）
* 优先选择饱和度最高的顶点
* @return 每个顶点的颜色数组
*/
public int[] dsaturColoring() {
int[] colors = new int[vertices];
Arrays.fill(colors, -1);
boolean[] colored = new boolean[vertices];
// 记录每个顶点的饱和度（已着色邻居的不同颜色数）
Set<Integer>[] saturationSets = new HashSet[vertices];
for (int i = 0; i < vertices; i++) {
saturationSets[i] = new HashSet<>();
}
// 第一步：选择度数最大的顶点，赋予颜色0
int maxDegreeVertex = 0;
for (int i = 1; i < vertices; i++) {
if (degree(i) > degree(maxDegreeVertex)) {
maxDegreeVertex = i;
}
}
colors[maxDegreeVertex] = 0;
colored[maxDegreeVertex] = true;
updateSaturation(maxDegreeVertex, colors, saturationSets);
// 后续步骤：每次选择饱和度最高的未着色顶点
for (int step = 1; step < vertices; step++) {
int selectedVertex = -1;
int maxSaturation = -1;
int maxDeg = -1;
for (int v = 0; v < vertices; v++) {
if (colored[v]) continue;
int sat = saturationSets[v].size();
int deg = degree(v);
// 优先选饱和度高的，饱和度相同选度数大的
if (sat > maxSaturation ||
(sat == maxSaturation && deg > maxDeg)) {
maxSaturation = sat;
maxDeg = deg;
selectedVertex = v;
}
}
// 为选中的顶点分配最小可用颜色
boolean[] usedColors = new boolean[vertices];
for (int neighbor : adjacencyList.get(selectedVertex)) {
if (colors[neighbor] != -1) {
usedColors[colors[neighbor]] = true;
}
}
for (int c = 0; c < vertices; c++) {
if (!usedColors[c]) {
colors[selectedVertex] = c;
break;
}
}
colored[selectedVertex] = true;
updateSaturation(selectedVertex, colors, saturationSets);
}
return colors;
}
/**
* 更新饱和度集合
*/
private void updateSaturation(int coloredVertex, int[] colors, Set<Integer>[] saturationSets) {
for (int neighbor : adjacencyList.get(coloredVertex)) {
if (colors[neighbor] == -1) {
saturationSets[neighbor].add(colors[coloredVertex]);
}
}
}
/**
* 普通贪心着色（按顶点编号顺序）
* 用于与Welsh-Powell和DSatur对比
*/
public int[] simpleGreedyColoring() {
int[] colors = new int[vertices];
Arrays.fill(colors, -1);
for (int v = 0; v < vertices; v++) {
boolean[] usedColors = new boolean[vertices];
for (int neighbor : adjacencyList.get(v)) {
if (colors[neighbor] != -1) {
usedColors[colors[neighbor]] = true;
}
}
for (int c = 0; c < vertices; c++) {
if (!usedColors[c]) {
colors[v] = c;
break;
}
}
}
return colors;
}
/**
* 回溯法精确求解色数（仅适用于小规模图 V <= 20）
* @return 最优着色方案
*/
public int[] exactColoring() {
if (vertices > 20) {
throw new IllegalArgumentException("精确算法仅适用于顶点数<=20的图");
}
int[] bestColors = new int[vertices];
int[] currentColors = new int[vertices];
Arrays.fill(bestColors, -1);
int[] bestColorCount = {vertices + 1};
backtrack(0, currentColors, 0, bestColors, bestColorCount);
return bestColors;
}
private void backtrack(int vertex, int[] currentColors, int colorCount,
int[] bestColors, int[] bestColorCount) {
if (vertex == vertices) {
if (colorCount < bestColorCount[0]) {
bestColorCount[0] = colorCount;
System.arraycopy(currentColors, 0, bestColors, 0, vertices);
}
return;
}
// 剪枝：如果当前使用的颜色数已经不小于最优解，停止搜索
if (colorCount >= bestColorCount[0]) {
return;
}
// 尝试所有已使用的颜色
boolean[] usedByNeighbors = new boolean[colorCount];
for (int neighbor : adjacencyList.get(vertex)) {
if (currentColors[neighbor] != -1 && currentColors[neighbor] < colorCount) {
usedByNeighbors[currentColors[neighbor]] = true;
}
}
for (int c = 0; c < colorCount; c++) {
if (!usedByNeighbors[c]) {
currentColors[vertex] = c;
backtrack(vertex + 1, currentColors, colorCount, bestColors, bestColorCount);
currentColors[vertex] = -1;
}
}
// 尝试使用新颜色
currentColors[vertex] = colorCount;
backtrack(vertex + 1, currentColors, colorCount + 1, bestColors, bestColorCount);
currentColors[vertex] = -1;
}
/**
* 计算色数（使用的颜色数量）
*/
public static int chromaticNumber(int[] colors) {
int max = -1;
for (int c : colors) {
max = Math.max(max, c);
}
return max + 1;
}
/**
* 验证着色是否合法
*/
public boolean isValidColoring(int[] colors) {
for (int v = 0; v < vertices; v++) {
if (colors[v] == -1) return false;
for (int neighbor : adjacencyList.get(v)) {
if (colors[v] == colors[neighbor]) {
return false;
}
}
}
return true;
}
/**
* 获取色数的下界（团数）和上界（最大度+1）
*/
public int[] colorNumberBounds() {
// 简单上界：最大度 + 1
int maxDegree = 0;
for (int v = 0; v < vertices; v++) {
maxDegree = Math.max(maxDegree, degree(v));
}
int upperBound = maxDegree + 1;
// 简单下界：最大团的大小（用贪心近似）
int lowerBound = approximateClique();
return new int[]{lowerBound, upperBound};
}
/**
* 近似最大团大小（作为色数下界）
*/
private int approximateClique() {
int maxClique = 1;
for (int v = 0; v < vertices; v++) {
Set<Integer> clique = new HashSet<>();
clique.add(v);
for (int u = v + 1; u < vertices; u++) {
boolean connectedToAll = true;
for (int c : clique) {
if (!adjacencyList.get(c).contains(u) && c != u) {
connectedToAll = false;
break;
}
}
if (connectedToAll) {
clique.add(u);
}
}
maxClique = Math.max(maxClique, clique.size());
}
return maxClique;
}
/**
* 打印着色结果（带颜色名称）
*/
public static void printColoring(int[] colors) {
String[] colorNames = {"红", "绿", "蓝", "黄", "紫", "橙", "粉", "青", "灰", "棕"};
for (int i = 0; i < colors.length; i++) {
String name = colors[i] < colorNames.length ? colorNames[colors[i]] : "C" + colors[i];
System.out.println("顶点 " + i + " -> " + name + " (" + colors[i] + ")");
}
System.out.println("总颜色数: " + chromaticNumber(colors));
}
public static void main(String[] args) {
// 构建示例图（Petersen图的一个子图）
GraphColoring graph = new GraphColoring(6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
graph.addEdge(3, 5);
graph.addEdge(4, 5);
System.out.println("=== 普通贪心着色 ===");
int[] simpleColors = graph.simpleGreedyColoring();
printColoring(simpleColors);
System.out.println("是否合法: " + graph.isValidColoring(simpleColors));
System.out.println("\n=== Welsh-Powell着色 ===");
int[] wpColors = graph.welshPowellColoring();
printColoring(wpColors);
System.out.println("是否合法: " + graph.isValidColoring(wpColors));
System.out.println("\n=== DSatur着色 ===");
int[] dsColors = graph.dsaturColoring();
printColoring(dsColors);
System.out.println("是否合法: " + graph.isValidColoring(dsColors));
System.out.println("\n=== 色数上下界 ===");
int[] bounds = graph.colorNumberBounds();
System.out.println("下界(团数): " + bounds[0] + ", 上界(最大度+1): " + bounds[1]);
System.out.println("\n=== 精确着色（小规模） ===");
int[] exactColors = graph.exactColoring();
printColoring(exactColors);
System.out.println("是否合法: " + graph.isValidColoring(exactColors));
}
}
四、复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 普通贪心 | O(V²) | O(V + E) | 按编号顺序，效果一般 |
| Welsh-Powell | O(V² + V log V) | O(V + E) | 按度数排序，效果较好 |
| DSatur | O(V³) | O(V + E) | 动态选择，效果最好 |
| 精确回溯 | O(V!) | O(V) | 保证最优，仅适用于小图 |
五、应用场景
- 课程表编排：冲突课程分配不同时段，最少时段数即色数
- 寄存器分配：编译器中冲突变量不能共用寄存器
- 频谱分配：相邻基站使用不同频段，最小化频段总数
- 地图着色：相邻区域使用不同颜色
- 任务调度：冲突任务分配到不同处理器或时间片
六、总结
本文实现了图着色问题的多种求解方法。Welsh-Powell和DSatur都是高效的贪心近似算法，DSatur在多数情况下能得到更少的颜色数。对于小规模图，精确回溯算法可以验证近似算法的质量。图着色作为NP完全问题的典型代表，其近似算法的研究对理解计算复杂性具有重要意义。
