xxx 图着色问题（贪心算法） 图着色问题是一个经典的图论问题，其目标是为图中的每个顶点分配一种颜色，使得任何两个相邻的顶点颜色不同，同时使用的颜色总数尽可能少。这个问题是NP-hard的，但贪心算法提供了一种简单且高效的近似解法。 题目描述 给定一个无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集合，\( E \) 是边集合。要求使用贪心算法对图进行着色，使得相邻顶点颜色不同，并尽量最小化颜色数量。 解题过程 贪心算法的核心思想是：按某种顺序遍历顶点，每次为当前顶点分配可用的最小颜色编号（即从颜色1开始检查，若与相邻顶点颜色不冲突则使用）。 顶点排序 贪心着色结果依赖于顶点处理顺序。常见策略包括： 随机顺序 ：按任意顺序处理顶点。 最大度优先 ：按顶点度降序处理（优先处理度数高的顶点，可能减少颜色数）。 饱和度排序 ：动态选择当前未着色顶点中相邻已着色颜色数最多的顶点（DSATUR算法）。 本例以 最大度优先 为例：计算每个顶点的度（相邻边数），按度从高到低排序。 颜色分配 初始化颜色数组 color[] ，初始值为0（表示未着色）。 创建颜色可用性数组 used[] ，记录临时不可用的颜色。 遍历排序后的顶点序列，对每个顶点 \( v \)： 检查所有邻接顶点，将已分配的颜色标记为不可用。 从颜色1开始递增查找第一个可用的颜色，分配给 \( v \)。 重置 used[] 为初始状态。 复杂度分析 时间复杂性：排序顶点需 \( O(|V|\log|V|) \)，着色过程需检查每条边（\( O(|E|) \)），总复杂度为 \( O(|V|\log|V| + |E|) \)。 空间复杂性：\( O(|V| + |E|) \) 存储图及颜色信息。 示例 考虑一个5顶点图：顶点A、B、C、D、E，边为 (A,B), (A,C), (B,C), (B,D), (C,D), (D,E)。 按度排序 ：B(度3)、C(度3)、A(度2)、D(度3)、E(度1) → 处理顺序为 B、C、A、D、E。 着色过程 ： B: 颜色1。 C: 邻接B(颜色1) → 颜色2。 A: 邻接B(1)、C(2) → 颜色3。 D: 邻接B(1)、C(2) → 颜色3（与A无冲突）。 E: 邻接D(3) → 颜色1。 最终使用3种颜色（注意此图色数为3，贪心解为最优）。 注意事项 贪心算法不保证得到最小颜色数（图着色是NP-hard），但实际中常得到较好近似解。 更优的排序策略（如DSATUR）可提升解质量，但增加计算开销。