PTA 上有一道图着色问题，估计很多刷过图的同学都见过：题目文字很简短，建模也一眼就能看懂，但真的上手提交后，不是超时就是边界情况判错，让人怀疑自己写了个假的回溯。这道题让我把图建模、搜索顺序、剪枝策略完整串了一遍，也踩了不少坑，所以把一路的思考过程、最终能稳定过判题机的写法和几个典型的错误现场整理出来。如果你正在刷图论题、准备算法课的上机考试，或者想搞懂“回溯 + 剪枝”到底是怎么从 O(k^n) 里挤出正确结果的，这篇应该能帮到你。

1. 先看懂题：图着色到底在考什么

1.1 数学定义与题目常见变体

图着色问题的标准定义其实一句话就能说清：给定一张无向图 G=(V,E)，还有一组颜色编号（比如 1 到 k），要求给每个顶点分配一种颜色，使得任意一条边的两个端点颜色不同。如果存在这样的分配，就说这张图是可以用 k 种颜色着色的，或者叫 k-可着色（k-colorable）。

但 PTA 这类判题平台上出现的“图着色问题”，经常会出成不同风格的变体，解题策略差别很大。我至少遇到过三种：

• 第一种最简单也最防不胜防：题目直接给出一张图和一组着色结果，要求判断这个着色方案是否合法。也就是只需要遍历所有边，查看每条边两端颜色是否相同，相同就非法，否则合法。这种题连搜索都用不上，但它会故意在输入格式上做文章，比如颜色编号可能不连续，可能给的是字符串，甚至给的“颜色数”根本没人用，迷惑性很强。
• 第二种是标准判定题：给定图和一个 k，问能否用不超过 k 种颜色完成着色。这是经典回溯的应用场景。
• 第三种是求最优解：不给你 k，要求输出这张图的最小着色数（色数）。这种需要在回溯过程中边搜边维护当前最优解，或者二分枚举 k 再反复调用判定函数。

为什么先说清楚变体？因为 PTA 的题面有时候会把“判断已给出的着色方案是否合法”这种简单题故意写得像要写搜索，很多同学上来就写 DFS，结果发现题目其实只让你做一遍线性检查，白白浪费时间，还可能因为先入为主的回溯逻辑产生多余的剪枝条件，把简单题写错。

1.2 为什么直觉解法是回溯而不是贪心

我第一次看到这道题的时候，第一反应是：直接按顺序贪心，每个顶点尽量用最小编号的颜色不行吗？这个想法在判断“能否合法着色”时通常有效，但一旦要算图的最小色数，贪心就靠不住了。

贪心算法（比如按顶点编号依次染色，每次选择一个与邻居不冲突的最小颜色）得到的颜色数高度依赖顶点的访问顺序。同一张图，换个顶点顺序，结果可能从 3 种变成 4 种甚至更多。经典教材里能找出很多贪心不是最优的例子，同时还有“先按度数从大到小排序再贪心”的启发式（也就是 Welsh-Powell 算法），它虽然能给出一个不错的上界，但仍然不保证最优。也就是说贪心只能给你一个“可能够用”的解，不能证明“最少需要多少种颜色”。

图着色的本质是组合搜索：每个顶点有 k 种颜色可选，所有方案构成一棵深度为 n、分支约为 k 的搜索树。回溯算法做的事就是在这棵树上做系统性的遍历，配合剪枝砍掉不可能的分支，从而保证：要么找到合法解，要么证明无解。所以对于“能否 k-着色”和“最小色数是几”这类精确问题，正确做法就是回溯。这个选择不是“喜欢搜索”，而是问题本身要求你在解空间中查找精确答案，贪心和近似算法只能做上界估计。

1.3 复杂度与“能过题”之间的边界

很多初学者一看回溯最坏复杂度 O(k^n) 就直接劝退，觉得这不可能是出题人想要的做法。但实际刷题时要看数据范围。我做过几道不同平台的图着色题，顶点数 n 一般给到 20 左右，最多不超过 30；k 可能给到 5 以内，也可能大到 n。这种规模下，回溯配合剪枝完全可以在毫秒级内出结果，反而是 O(2^n * n) 之类的 DP 在某些情况下更麻烦。

对于这种“指数级但规模小”的题目，关键不是追求多项式算法，而是把搜索树的实际分支数砍下来。核心就是：搜索顺序是否合理、剪枝是否到位、状态检查是否高效。这三件事做好之后，后面代码的差距会非常大。我当时就是先写了一个朴素回溯，样例能过，但构造一个 25 个顶点的稠密图就跑到几秒；把剪枝策略加上去之后，同样的数据瞬间出结果。所以不要一看到指数复杂度就慌，要看 n 的边界和剪枝空间。

2. 核心算法设计：回溯框架与剪枝策略

2.1 状态表示与建图方式

先聊建图。图着色题里顶点数通常不大，用邻接矩阵最直观，判断“两个顶点是否相邻”是 O(1)。如果顶点数达到几千，那建议用邻接表，但图着色精确搜索的题一般不会给这么大，邻接矩阵性价比最高。

存储上用一个二维布尔数组edge[u][v]表示 u 和 v 之间有边。同时维护一个order[]数组，里面记录搜索时处理顶点的顺序。我刚写的时候直接用顶点编号 0 到 n-1 作为顺序，后来才发现这个顺序对回溯性能影响非常大。

颜色状态用color[u]表示顶点 u 当前被染的颜色，取 1 到当前最大色号。未染色的顶点为 0。还有一个重要的量是used，表示当前搜索路径上已经使用了多少种颜色。注意我用的是“最大颜色编号”，因为在颜色对称性下，只要记录了已经用了哪些颜色类别，新颜色永远可以分配一个新编号 used+1，而不需要枚举 used 之后的所有数字。

为什么维护 used 而不是每个顶点的颜色数组就够了？因为剪枝时需要快速知道“当前深度已经用了几种颜色”，如果已经超过已知最优解 ans，这棵树就没有继续走的意义，可以直接返回。

2.2 三类关键剪枝：对称性、邻域检查、搜索顺序

第一个剪枝是颜色对称性剪枝。颜色名字本身没有意义，只是区分不同颜色而已。方案 {A:1, B:2, C:3} 和方案 {A:2, B:1, C:3} 本质上是一样的，只是颜色标签互换。因此，搜索时可以强制第一个顶点染颜色 1，不用尝试其他颜色。更进一步，在尝试当前顶点颜色时，不需要尝试所有正整数，只需要尝试“已经出现过的颜色”再加“一个新颜色编号”就够了。因为任何又一个全新颜色，无论编号是几，在对称意义上是同一个选择。我写的代码里，新颜色只尝试used+1这一个编号，就是利用这个道理。这一条剪枝能把搜索树从“按 k 种颜色尝试”变成“按已用颜色类别 + 1 个新颜色尝试”，对于初始阶段尤其有效。

第二个剪枝是邻域颜色冲突检查。检查一个颜色 c 能不能给顶点 u 用，最朴素的做法是遍历 u 的所有邻居，看看有没有邻居已经染了 c，复杂度 O(deg(u))。如果每次尝试都做一遍，累加起来会很大。常见的优化是维护一个“邻域颜色占用表”，但更简洁的做法是位掩码。因为 n 不超过 30 时，可以用一个 int 的第 i 位表示顶点 i；adjMask[u]存 u 的邻居集合，colorMask[c]存“染了颜色 c 的所有顶点集合”。那么 c 能不能给 u 用，只需要判断(adjMask[u] & colorMask[c])是否为 0。这一步从遍历邻居变成一次位与运算，速度提升非常明显。

第三个剪枝是搜索顺序。搜索树的深度是固定的（每个顶点都要着色），但分支宽度受顺序影响很大。经验法则是：度数大的顶点先染。因为度数大的顶点约束最强，先处理它能更早暴露冲突，从而剪掉大量后续分支。这个思路类似于约束传播里的“MRV 最小剩余值启发式”：哪一步最受限制，就先尝试哪一步。实现时只需要按度数做一次排序，得到order[]，DFS 时按下标顺序取顶点即可。

还有一个常用的小技巧是“当前已用颜色数 used”剪枝：如果used >= ans，说明当前这条搜索路径即使继续走下去，也不可能优于已经找到的最优解，直接返回。这个是求最小色数的关键剪枝，它会让搜索过程越来越快——因为一旦找到一个比较小的可行解，大量分支就会被这个条件砍掉。

2.3 回溯流程的伪代码

把上面的思路串成回溯框架，大概是这样的：

order[] = 按度数降序排列的顶点序列 color[order[0]] = 1 dfs(step = 1, used = 1): 如果 step == n: ans = min(ans, used) return 当前顶点 u = order[step] 对 c = 1 到 used + 1: 如果 c 与 u 的邻居颜色冲突: continue color[u] = c dfs(step + 1, max(used, c)) color[u] = 0

注意这里外层循环不需要从 1 枚举到 n 甚至到很大的数，只枚举 1 到 used+1，同时used+1只代表“使用一种新颜色”。这样既覆盖了所有可能结果，又避免了大量对称的冗余搜索。我在实际实现里还把第一个顶点固定为颜色 1，dfs 从第二个顶点开始，起点直接少了一个因子。

3. 从暴力到能过题：代码实现与逐段解析

3.1 求最小着色数的完整参考实现

下面这段代码是我调过很多次之后最终稳定过判题机的版本，逻辑是直接求最小色数。判定型题目（给定 k 问是否可行）只要判断最后求出来的ans <= k即可。

#include <bits/stdc++.h> using namespace std; const int MAXN = 30; int n, m; bool edge[MAXN][MAXN]; int deg[MAXN], order[MAXN]; int color[MAXN]; int ans; void dfs(int step, int used) { if (used >= ans) return; if (step == n) { ans = min(ans, used); return; } int u = order[step]; // 只尝试已有颜色 + 一个全新颜色 for (int c = 1; c <= used + 1; ++c) { bool conflict = false; for (int v = 0; v < n; ++v) { if (edge[u][v] && color[v] == c) { conflict = true; break; } } if (conflict) continue; color[u] = c; dfs(step + 1, max(used, c)); color[u] = 0; // 如果当前已经用颜色数达到 ans-1，且刚才尝试的是新颜色，后面不必再试 if (c == used + 1 && used + 1 >= ans) break; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 这里以单组数据为例，多组数据记得在主循环内初始化数组 cin >> n >> m; for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; // 根据题目，顶点编号可能是 0 开头也可能是 1 开头 edge[u][v] = edge[v][u] = true; deg[u]++; deg[v]++; } for (int i = 0; i < n; ++i) order[i] = i; sort(order, order + n, [&](int a, int b) { if (deg[a] != deg[b]) return deg[a] > deg[b]; return a < b; }); ans = n; // 最坏情况每个顶点独立一种颜色 color[order[0]] = 1; dfs(1, 1); cout << ans << "\n"; return 0; }

代码不长，但每一部分都有讲究。我逐个拆开说。

3.2 关键代码段：DFS 核心逻辑解释

先看 DFS 开头的那行if (used >= ans) return;。这是整个程序里最有效的一条剪枝，它保证任何一条搜索路径在超过当前已知最优解时立刻终止。ans 一开始等于 n，所以这个剪枝在前期不生效，但随着搜索进行、ans 不断被更新为更小的值，剪枝力度会越来越大。这也是为什么我建议不要用二分枚举 k + 判定函数来解这题，而是直接一遍 DFS 找最优：后者的 ans 剪枝是动态的，搜索过程中一旦找到更小的解，立刻就能砍掉大量后续分支。

for (int c = 1; c <= used + 1; ++c)这行的设计我非常喜欢，也很关键。它只用尝试“当前已经出现过的颜色”以及“开一个新颜色”。比如当前已经用了 3 种颜色，那么下一个顶点要么染这 3 种颜色之一，要么选择第 4 种新颜色。在上面这种写法下，新颜色编号永远是 used+1，之前的顶点如果用了颜色 5 而 used=3，说明这个 5 是多余的、不存在的，因为新颜色的引入顺序一定是从 1 到 2 到 3 依次出现的。这种“只新增一个颜色编号”的处理，其实就是对称性剪枝的一种具象化。

冲突检查的部分，我先用邻居遍历判断。这个版本在 n=25~30 时已经能很快跑完，因为剪枝已经把分支数压得很低。如果希望再压榨性能，可以把冲突检查替换成位掩码版本，后面会单独说。

3.3 位掩码优化：从 O(deg) 到 O(1) 的检查

当 n 不超过 30 时，可以用 int 的每一个二进制位表示一个顶点。改造后的核心片段大概是：

int adjMask[MAXN]; // 每个顶点的邻居集合掩码 int colorMask[MAXN]; // 每种颜色对应的顶点集合掩码 // 注意 MAXN 是颜色上限，不是顶点数 bool dfs(int step, int used) { if (used >= ans) return false; if (step == n) return true; int u = order[step]; for (int c = 1; c <= used + 1; ++c) { if (adjMask[u] & colorMask[c]) continue; // 有冲突 colorMask[c] |= (1 << u); if (dfs(step + 1, max(used, c))) return true; colorMask[c] ^= (1 << u); } return false; }

这个版本有两个细节要注意：一是colorMask下标是颜色号，数组大小要开到MAXN或题目给的 k 的上限，别只开 n；二是回溯时用异或^= (1<<u)比-=更稳妥，因为同一轮中这个位只可能被当前层设置，异或一定可以还原。用位掩码之后，检查冲突从遍历所有邻居变成一次&运算，搜索速度会有很直观的提升。如果 n 超过 30，把 int 换成std::bitset<MAXN>即可，原理一样，只是位运算成本略高。

做完位掩码改造后我在本地测试过，25 个顶点、所有顶点两两相连（完全图）的情况下，搜索会非常快地发现需要 n 种颜色，证明“度数大先染”的排序在这里也起到了重要作用——它让我们第一眼就集中处理最难的顶点，快速逼近答案。

3.4 另一种变体：给定方案判断合法性的极简解法

如果题面给的是“已经染好色的方案，问是否合法”，那完全不需要上面的回溯。直接扫描所有边：

bool ok = true; for (int u = 0; u < n && ok; ++u) { for (int v = u + 1; v < n; ++v) { if (edge[u][v] && color[u] == color[v]) { ok = false; break; } } }

这个解法的复杂度是 O(n^2)（或 O(m) 如果用邻接表扫边），几乎不会超时。难题往往在输入的读取上：比如颜色编号可能用空格分隔但行尾有多余空格，或者颜色数 k 和实际用到的颜色种类对不上，甚至有些顶点可能没有染色（颜色为 0）。所以接到这种题，第一件事不是写搜索，而是确认清楚“它到底要我求什么”。

4. 调试实录：我在这道题上踩过的坑

4.1 WA：输出格式与颜色编号不连续

我第一次提交 WA 的时候，一度以为是回溯逻辑写错了，后来对比题目样例才发现是输出格式问题：题目要求输出Yes/No，我写成了YES/NO。这个错误很低级，但判题机不看大小写宽容度，所以刷题时务必连样例输出的大小写、空格、换行都逐字对照。

另一个隐蔽的 WA 原因是颜色编号不连续。题目说颜色范围是 1 到 k，但给出的顶点颜色可能只用了编号 2 和 5，没有 1、3、4。如果是“判断给定方案是否合法”的板子，我代码里只检查相邻点颜色是否相等，不受编号影响，不会出问题。但如果我自作聪明地写“颜色编号必须 ≤ k”或者“颜色编号必须 ≥ 1”，就可能导致误判。判断合法性只关心“相邻是否相等”，不关心颜色编号本身是否连续。

4.2 TLE：朴素回溯和剪枝的差距有多大

我也写过完全不带剪枝的版本：递归函数遍历每个顶点的所有颜色 1 到 n，不固定首顶点颜色，也不按度数排序。结果在 n=20 的随机图上勉强跑完，到了 n=26 就完全卡住。加上“固定首色 + 只试 used+1 + 度数降序 + used≥ans 剪枝”之后，同一个测试数据运行时间从几十秒降到了十几毫秒。这个差距是我亲身感受到的，也是建议所有刷这题的同学都要做一次对比实验的原因。

如果还是超时，可以再检查两个地方：一是邻接矩阵是否初始化干净。多组测试数据时，如果 edge 数组没清零，上一组数据残留的边会让图变稠密，冲突变多，但搜索时间反而可能增加，因为解空间被污染。二是有没有写ios::sync_with_stdio(false)，在数据量稍大的题目里，这个开关带来的速度差异还是能感觉到的。

4.3 RE：数组越界与顶点编号从 1 开始

数组越界主要发生在两个场景。场景一是colorMask数组只开了 n 大小，但颜色编号可能达到 n，访问colorMask[used+1]时越界。场景二是顶点编号从 1 开始输入，但数组定义成edge[MAXN][MAXN]后我访问了edge[0][v]，没有为下标 0 留出空间，或者干脆读入的时候忘了把 u、v 减一。

这类问题在 PTA 上通常表现为运行时错误或答案错误而不是编译错误，所以非常恼人。我的习惯是拿到题先看输入约定：如果顶点编号是从 1 到 n，我可以直接把数组开到 MAXN+1，并且把 n+1 作为上界读取，这样省去每次减一的麻烦；如果直接减一，就要保证所有循环下标从 0 开始。两种策略都行，但别在一段代码里混用。

4.4 常见问题速查表

5. 延伸：从这道题到实际应用与进阶思考

5.1 图着色在排课和资源分配里的影子

图着色问题在算法竞赛之外的应用非常广。最经典的是排课：把每门课当作顶点，如果两门课有学生同时选修，就在它们之间连一条边；着色得到的最小颜色数，就是安排互不冲突的考试时段所需的最少时段数。类似的还有寄存器分配（两个同时活跃的变量不能放在同一个寄存器，就是一条冲突边）、无线频段分配（覆盖区域重叠的基站不能使用同一频段），以及 Sudoku（每个格子是顶点，同一行、列、宫内互连，9 种颜色对应 9 个数字）。

理解了这道题背后的模型，再去面试或者做系统设计时遇到“给资源分配最少种类数”的问题，就能很快往图着色方向靠。很多时候难点不在代码，而在你能不能把业务约束抽象成“冲突边”。

5.2 更进一步的搜索优化：DSATUR 与分支定界

回溯 + 剪枝已经能过大多数小规模图着色题，但如果想再提升，有一个经典启发式叫 DSATUR（Dynamic Saturation Degree）。它的思想是：每次选择“当前已用颜色数最多的未着色顶点”来扩展，也就是饱和度最大的顶点。直观解释是，这种顶点可选颜色最少，最容易产生冲突，优先处理它能更早剪枝。DSATUR 在不少大规模着色问题上表现很好，但它本质上还是回溯搜索的变体，只是改变了顶点选择顺序和颜色顺序。PTA 的题一般用不上，不过作为扩展了解，对加深搜索算法理解有帮助。

还有一类更“算法竞赛味”的做法是：二分枚举颜色数 k，并把“是否存在合法 k-着色”转成约束满足问题，用位运算 + 精确覆盖思想求解。但在这个题的规模下没有必要，反而是直接求最小色数的剪枝效率更高。我做过的几次对比里，直接 DFS 维护 ans 比“二分 + 多次判定”更容易过题，原因也很简单：后者每次判定都要重新搜索整棵树，而前者的 ans 会随着搜索逐步收紧，相当于把多次搜索的剪枝累积在了一起。

5.3 如果想把这套代码变成模板

这套回溯框架不仅适用于图着色，还能迁移到其他组合搜索问题，比如数独、N 皇后、最大独立集等。它们的共同点是：状态可以拆成“逐个位置赋值”，约束是“局部冲突”，目标是“找可行解或最优解”。我的建议是把这个框架的关键剪枝策略抽象成自己的模板：固定第一个选择、只处理“已有 + 一个新增”的选项、按约束强度决定搜索顺序、维护当前最优结果用于剪枝。这四条在非常多题目里都通用。

就我自己的体验来说，真正把这个题目吃透的标志，不是能背出代码，而是能不看代码解释清楚“为什么固定首色是对的”“为什么只试 used+1 不会漏解”“为什么度数大的顶点先处理能加速”。把这几个为什么想明白，以后遇到类似的搜索题，你也能更快地设计出属于自己的剪枝策略。