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 左右最多不超过 30k 可能给到 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表示当前搜索路径上已经使用了多少种颜色。注意我用的是“最大颜色编号”因为在颜色对称性下只要记录了已经用了哪些颜色类别新颜色永远可以分配一个新编号 used1而不需要枚举 used 之后的所有数字。为什么维护 used 而不是每个顶点的颜色数组就够了因为剪枝时需要快速知道“当前深度已经用了几种颜色”如果已经超过已知最优解 ans这棵树就没有继续走的意义可以直接返回。2.2 三类关键剪枝对称性、邻域检查、搜索顺序第一个剪枝是颜色对称性剪枝。颜色名字本身没有意义只是区分不同颜色而已。方案 {A:1, B:2, C:3} 和方案 {A:2, B:1, C:3} 本质上是一样的只是颜色标签互换。因此搜索时可以强制第一个顶点染颜色 1不用尝试其他颜色。更进一步在尝试当前顶点颜色时不需要尝试所有正整数只需要尝试“已经出现过的颜色”再加“一个新颜色编号”就够了。因为任何又一个全新颜色无论编号是几在对称意义上是同一个选择。我写的代码里新颜色只尝试used1这一个编号就是利用这个道理。这一条剪枝能把搜索树从“按 k 种颜色尝试”变成“按已用颜色类别 1 个新颜色尝试”对于初始阶段尤其有效。第二个剪枝是邻域颜色冲突检查。检查一个颜色 c 能不能给顶点 u 用最朴素的做法是遍历 u 的所有邻居看看有没有邻居已经染了 c复杂度 O(deg(u))。如果每次尝试都做一遍累加起来会很大。常见的优化是维护一个“邻域颜色占用表”但更简洁的做法是位掩码。因为 n 不超过 30 时可以用一个 int 的第 i 位表示顶点 iadjMask[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 到 used1同时used1只代表“使用一种新颜色”。这样既覆盖了所有可能结果又避免了大量对称的冗余搜索。我在实际实现里还把第一个顶点固定为颜色 1dfs 从第二个顶点开始起点直接少了一个因子。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 种新颜色。在上面这种写法下新颜色编号永远是 used1之前的顶点如果用了颜色 5 而 used3说明这个 5 是多余的、不存在的因为新颜色的引入顺序一定是从 1 到 2 到 3 依次出现的。这种“只新增一个颜色编号”的处理其实就是对称性剪枝的一种具象化。冲突检查的部分我先用邻居遍历判断。这个版本在 n25~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二是回溯时用异或^ (1u)比-更稳妥因为同一轮中这个位只可能被当前层设置异或一定可以还原。用位掩码之后检查冲突从遍历所有邻居变成一次运算搜索速度会有很直观的提升。如果 n 超过 30把 int 换成std::bitsetMAXN即可原理一样只是位运算成本略高。做完位掩码改造后我在本地测试过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不固定首顶点颜色也不按度数排序。结果在 n20 的随机图上勉强跑完到了 n26 就完全卡住。加上“固定首色 只试 used1 度数降序 used≥ans 剪枝”之后同一个测试数据运行时间从几十秒降到了十几毫秒。这个差距是我亲身感受到的也是建议所有刷这题的同学都要做一次对比实验的原因。如果还是超时可以再检查两个地方一是邻接矩阵是否初始化干净。多组测试数据时如果 edge 数组没清零上一组数据残留的边会让图变稠密冲突变多但搜索时间反而可能增加因为解空间被污染。二是有没有写ios::sync_with_stdio(false)在数据量稍大的题目里这个开关带来的速度差异还是能感觉到的。4.3 RE数组越界与顶点编号从 1 开始数组越界主要发生在两个场景。场景一是colorMask数组只开了 n 大小但颜色编号可能达到 n访问colorMask[used1]时越界。场景二是顶点编号从 1 开始输入但数组定义成edge[MAXN][MAXN]后我访问了edge[0][v]没有为下标 0 留出空间或者干脆读入的时候忘了把 u、v 减一。这类问题在 PTA 上通常表现为运行时错误或答案错误而不是编译错误所以非常恼人。我的习惯是拿到题先看输入约定如果顶点编号是从 1 到 n我可以直接把数组开到 MAXN1并且把 n1 作为上界读取这样省去每次减一的麻烦如果直接减一就要保证所有循环下标从 0 开始。两种策略都行但别在一段代码里混用。4.4 常见问题速查表现象可能原因处理思路WA 且样例能过输出大小写、多空格、多换行逐字比对样例输出格式WA 且只错大图多组数据未清空 edge/color每次循环前初始化数组TLE没有固定首色、遍历全部颜色编号增加对称性剪枝只试 used1TLE冲突检查遍历邻居太慢换成位掩码(adjMask colorMask)REcolorMask/邻接矩阵下标越界注意顶点编号从 0 还是 1 开始结果偏大贪心代替回溯求最小色数确认题目要求精确解用 DFS 搜索5. 延伸从这道题到实际应用与进阶思考5.1 图着色在排课和资源分配里的影子图着色问题在算法竞赛之外的应用非常广。最经典的是排课把每门课当作顶点如果两门课有学生同时选修就在它们之间连一条边着色得到的最小颜色数就是安排互不冲突的考试时段所需的最少时段数。类似的还有寄存器分配两个同时活跃的变量不能放在同一个寄存器就是一条冲突边、无线频段分配覆盖区域重叠的基站不能使用同一频段以及 Sudoku每个格子是顶点同一行、列、宫内互连9 种颜色对应 9 个数字。理解了这道题背后的模型再去面试或者做系统设计时遇到“给资源分配最少种类数”的问题就能很快往图着色方向靠。很多时候难点不在代码而在你能不能把业务约束抽象成“冲突边”。5.2 更进一步的搜索优化DSATUR 与分支定界回溯 剪枝已经能过大多数小规模图着色题但如果想再提升有一个经典启发式叫 DSATURDynamic Saturation Degree。它的思想是每次选择“当前已用颜色数最多的未着色顶点”来扩展也就是饱和度最大的顶点。直观解释是这种顶点可选颜色最少最容易产生冲突优先处理它能更早剪枝。DSATUR 在不少大规模着色问题上表现很好但它本质上还是回溯搜索的变体只是改变了顶点选择顺序和颜色顺序。PTA 的题一般用不上不过作为扩展了解对加深搜索算法理解有帮助。还有一类更“算法竞赛味”的做法是二分枚举颜色数 k并把“是否存在合法 k-着色”转成约束满足问题用位运算 精确覆盖思想求解。但在这个题的规模下没有必要反而是直接求最小色数的剪枝效率更高。我做过的几次对比里直接 DFS 维护 ans 比“二分 多次判定”更容易过题原因也很简单后者每次判定都要重新搜索整棵树而前者的 ans 会随着搜索逐步收紧相当于把多次搜索的剪枝累积在了一起。5.3 如果想把这套代码变成模板这套回溯框架不仅适用于图着色还能迁移到其他组合搜索问题比如数独、N 皇后、最大独立集等。它们的共同点是状态可以拆成“逐个位置赋值”约束是“局部冲突”目标是“找可行解或最优解”。我的建议是把这个框架的关键剪枝策略抽象成自己的模板固定第一个选择、只处理“已有 一个新增”的选项、按约束强度决定搜索顺序、维护当前最优结果用于剪枝。这四条在非常多题目里都通用。就我自己的体验来说真正把这个题目吃透的标志不是能背出代码而是能不看代码解释清楚“为什么固定首色是对的”“为什么只试 used1 不会漏解”“为什么度数大的顶点先处理能加速”。把这几个为什么想明白以后遇到类似的搜索题你也能更快地设计出属于自己的剪枝策略。