PAT甲级1154题：图顶点着色问题解析与实现

一、问题背景与定义

PAT甲级1154题“Vertex Coloring”是图论领域的经典问题，要求对无向图的顶点进行着色，使得相邻顶点颜色不同，且使用的颜色总数最少。该问题在计算机科学中具有广泛应用，例如任务调度、频谱分配、寄存器分配等场景。其核心目标是通过算法找到图的最小着色数（Chromatic Number），即满足条件的最小颜色数量。

问题输入与输出

输入通常包含两部分：

顶点数量 (N) 和边数量 (M)。
(M) 条边，每条边由两个顶点编号组成，表示顶点间的连接关系。

输出要求为最小着色数 (K)，以及一种具体的着色方案（若题目要求）。

示例分析

假设输入为：

表示有5个顶点（0-4）和4条边。通过分析可知，该图为一条链状结构，最小着色数为2（交替着色）。

二、图着色算法原理

1. 贪心算法（Greedy Algorithm）

贪心算法是最常用的近似解法，其核心思想是按顺序处理顶点，并为每个顶点分配当前可用的最小颜色编号。具体步骤如下：

初始化所有顶点颜色为未分配（如-1）。
按顶点编号顺序遍历每个顶点。
对于当前顶点，检查所有相邻顶点的颜色，记录未使用的最小颜色。
将该颜色分配给当前顶点。

代码示例（C++）：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int vertexColoring(int N, vector<vector<int>>& edges) {
    vector<vector<int>> adj(N); // 邻接表
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    vector<int> color(N, -1);
    for (int i = 0; i < N; ++i) {
        vector<bool> used(N, false);
        for (int neighbor : adj[i]) {
            if (color[neighbor] != -1) {
                used[color[neighbor]] = true;
            }
        }
        // 找到第一个未使用的颜色
        for (int c = 0; c < N; ++c) {
            if (!used[c]) {
                color[i] = c;
                break;
            }
        }
    }
    return *max_element(color.begin(), color.end()) + 1; // 最大颜色编号+1
}

局限性：贪心算法的结果依赖于顶点处理顺序，可能无法得到最小着色数，但能保证颜色数不超过 (\Delta + 1)（(\Delta) 为最大度数）。

2. 回溯算法（Backtracking）

回溯算法通过递归尝试所有可能的颜色分配，并在发现冲突时回溯，适用于小规模图。其步骤如下：

从第一个顶点开始，尝试所有颜色。
对于当前颜色，检查是否与相邻顶点冲突。
若无冲突，递归处理下一个顶点；否则尝试下一种颜色。
若所有颜色均冲突，回溯到上一顶点。

优化策略：

剪枝：提前终止不可能的分支（如剩余顶点数超过剩余颜色数）。
排序顶点：优先处理度数高的顶点（DSATUR算法思想）。

代码示例（Python）：

def is_safe(graph, color, v, c):
    for neighbor in graph[v]:
        if color[neighbor] == c:
            return False
    return True
def backtrack(graph, color, v, m):
    if v == len(graph):
        return True
    for c in range(1, m + 1):
        if is_safe(graph, color, v, c):
            color[v] = c
            if backtrack(graph, color, v + 1, m):
                return True
            color[v] = 0  # 回溯
    return False
def vertex_coloring(graph, m):
    color = [0] * len(graph)
    if backtrack(graph, color, 0, m):
        return color
    else:
        return None

3. 高级算法

DSATUR算法：优先处理度数饱和度高的顶点，减少颜色冲突。
遗传算法：通过模拟进化过程优化着色方案，适用于大规模图。
线性规划：将问题转化为整数线性规划，使用求解器（如CPLEX）获取精确解。

三、实现步骤与优化

1. 输入处理与图构建

使用邻接表或邻接矩阵存储图结构。
示例：将输入边转换为邻接表 vector<vector<int>> adj。

2. 贪心算法优化

颜色数组初始化：初始时所有顶点颜色为-1。
冲突检测优化：使用位运算或布尔数组快速标记已用颜色。
顺序优化：按顶点度数从高到低处理（Welsh-Powell算法）。

优化代码片段：

// 按度数排序顶点
vector<pair<int, int>> vertices;
for (int i = 0; i < N; ++i) {
    vertices.emplace_back(adj[i].size(), i);
}
sort(vertices.rbegin(), vertices.rend()); // 度数降序
vector<int> color(N, -1);
for (auto& [deg, v] : vertices) {
    vector<bool> used(N, false);
    for (int neighbor : adj[v]) {
        if (color[neighbor] != -1) {
            used[color[neighbor]] = true;
        }
    }
    for (int c = 0; c < N; ++c) {
        if (!used[c]) {
            color[v] = c;
            break;
        }
    }
}

3. 回溯算法优化

最小剩余值（MRV）：优先处理可选颜色最少的顶点。
前向检查：在分配颜色时，立即标记相邻顶点的不可用颜色。

四、性能分析与注意事项

1. 时间复杂度

贪心算法：(O(N^2))（每个顶点需检查所有相邻顶点）。
回溯算法：最坏情况下为指数级 (O(m^N))（(m) 为颜色数）。

2. 空间复杂度

邻接表：(O(N + M))。
颜色数组：(O(N))。

3. 实际应用建议

小规模图：优先使用回溯或DSATUR算法，确保最小着色数。
大规模图：采用贪心算法或启发式方法，平衡效率与结果质量。
并行化：对独立子图可并行处理（如分治策略）。

五、总结与扩展

PAT甲级1154题“Vertex Coloring”是图论算法的典型应用，通过贪心、回溯等策略可有效解决。实际开发中，需根据图规模和精度要求选择合适算法。进一步研究可关注：

分布式图着色：适用于超大规模图（如社交网络）。
动态图着色：处理顶点或边动态变化的场景。
与机器学习结合：利用神经网络预测着色方案。

通过深入理解图着色问题的原理与实现，开发者能够更好地应对资源分配、任务调度等领域的挑战，提升系统效率与可靠性。