无线广播问题与二分图判定：BFS染色法详解

做了这么多年 OJ能在第一眼就让人产生这题有点东西感觉的图论题不多无线广播Broadcast算一个。光看名字容易以为是通信专业的网络规划题什么信号覆盖、信道分配、广播站点读题像是在看工程文档。可实际上这是一道纯粹的图论问题给你一张无向图问能不能用两种颜色给所有顶点染色使每条边两端的颜色不同。用行话讲就是判断这张图是不是二分图。我第一次见到这道题是在某高校 OJ 的图论专题里。当时刚学完 BFS脑子一热就想用最短路硬做交上去一排 WA 把我打醒了。后来冷静下来把题面翻译成图模型十分钟就过了。这篇文章我把完整的建模思路、算法流程、参考代码和一些容易踩的坑都整理出来适合刚学完图遍历、想在真题里练手的同学也适合准备面试手撕算法、想快速复习二分图判定的朋友。1. 先把广播场景翻译成图论模型1.1 从题面到顶点和边的映射先把题面场景还原一下。广播网络里有若干节点通常是发射塔或基站节点之间只要距离足够近就能直接通信形成一条通路。现在要给每个节点分配一个广播通道规则是任何两个存在直接通路的节点它们的通道必须不一样。题目只提供两种通道问有没有可能做到。这几乎就是为图论量身定做的场景节点对应图的顶点节点之间的直接通路对应无向边两种通道对应两种颜色相邻节点通道必须不同对应相邻顶点颜色必须不同。做完这层映射问题的真面目就露出来了给定一张无向图能否用两种颜色给所有顶点合法染色使得任意一条边的两个端点颜色不同这就是标准的二分图判定问题也叫二染色问题。1.2 为什么两种通道等价于二染色把话说得更细一点。二染色要求把顶点分成两个集合集合内部的点之间可以有任意关系但所有边都必须横跨两个集合不允许出现集合内部的边。一旦出现内部边这条边两端的颜色就必然相同直接违反规则。反过来只要一张图能二染色就等价于存在一个顶点划分把图分成左右两组所有边都在两组之间。这个性质和广播问题里的约束是一一对应的颜色 1 的节点用通道 A颜色 2 的节点用通道 B相邻的两个节点必然落在不同集合通道也就必然不同。这里有个判断捷径一张图能二染色当且仅当它不含长度为奇数的环。三角形的三个顶点两两相连环长度为 3是奇数所以三角形永远无法用两种颜色合法染色这就是无线广播题里输出 NO 的核心原因。相反四边形4 环就能染A 染 1、B 染 2、C 染 1、D 染 2首尾检查一遍全部合法。提示学有余力的话可以自己证明奇数环是二分图的唯一障碍。思路是从环上任一点出发沿环走一圈每走一条边颜色就切换一次走完一个长度为奇数的环回到起点时颜色恰好被切换了奇数次起点自己的颜色和自己冲突。2. 核心算法BFS 染色法完整拆解2.1 染色流程的通俗版和正式版通俗地说这题就是给地图涂色规则是接壤区域必须异色。手动操作流程是随便找一块还没涂色的区域涂成红色然后所有和它接壤的区域涂蓝色所有和蓝色接壤的区域再涂红色一路铺开直到这块连通区域全部涂完。铺的过程中发现某个区域已经被涂过色而且颜色和当前要求的颜色冲突那么整张图宣告失败。正式化的算法步骤是这样的用 color 数组记录每个顶点的颜色0 表示未染色1 和 2 表示两种颜色遍历所有顶点凡是遇到 color 为 0 的顶点就把它作为起点启动一次 BFSBFS 中起点染成 1每次从队列取出顶点 u遍历它的所有邻居 v如果 v 未染色染成3 - color[u]也就是和 u 相反的颜色然后入队如果 v 已经染色检查它和 u 的颜色是否相同相同则直接返回失败所有起点都 BFS 完且没有冲突整体可行。3 - color[u]是一个很实用的小技巧。color 取值只有 1 和 2当 u 是 1 时结果是 2u 是 2 时结果是 1一行代码完成颜色切换不用写 if-else。这个写法在很多染色类题目里都能复用。2.2 为什么 BFS 染色不会漏解也不会假阳性需要解释一个很多人会问的问题为什么 BFS 染一遍就能下结论不会漏掉某些情况关键在于图里的关系是沿着边传递的。一旦起点颜色确定和它直接相连的顶点颜色就被强制确定这些顶点又继续强制它们的邻居……整个过程只有一条逻辑链。BFS 从起点开始一层一层把整个连通分量扫完每个被访问的顶点都只可能有一种被强制决定的颜色。如果颜色没有冲突说明这个连通分量确实存在一种一致的颜色安排如果出现冲突说明无论怎么调整起点颜色都无法避免因为起点颜色翻转后整个连通分量的颜色只会整体互换冲突点依然冲突。另一个常见误区是对非连通图处理不到位。图可能由多个互不相连的连通分量组成比如顶点 1、2 之间有边顶点 3、4 之间有边但两组之间没有任何通路。如果只从 1 号顶点做一次 BFS顶点 3、4 根本访问不到程序会漏判。所以算法第 2 步的外层循环是这个题的关键每个未染色顶点都要当作起点跑一遍。每个连通分量的起点颜色互相独立是选 1 还是选 2 不影响整体可行性。2.3 建图方式和复杂度分析建图用邻接表。顶点数通常到十万级别甚至更高邻接矩阵的话空间是顶点数的平方直接爆炸所以必须用vectorint adj[MAXN]这种动态数组。每读入一条边 a-b就在 a 的邻接表里加入 b在 b 的邻接表里加入 a因为这是无向图。时间上每个顶点入队一次每条边作为邻居被检查两次两个方向各一次总复杂度 O(N M)。这个量级在绝大多数 OJ 上都是秒过不需要任何额外的剪枝优化。需要警惕的是递归 DFS 版本——如果图是一条超长链比如十万个节点串成一串递归深度就是十万超出默认栈空间会段错误。所以除非评测环境明确提供了足够的栈空间否则首选 BFS。3. 实操记录从读题到 AC 的完整链路3.1 一份实测可用的参考实现下面这份 C 代码是完整可提交的我在不同学校的评测环境里都跑过没有依赖特殊编译选项直接交就行#include cstdio #include cstring #include vector #include queue using namespace std; const int MAXN 100005; vectorint adj[MAXN]; int color[MAXN]; bool bfs(int s) { queueint q; color[s] 1; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (color[v] 0) { color[v] 3 - color[u]; q.push(v); } else if (color[v] color[u]) { return false; } } } return true; } int main() { int n, m; while (scanf(%d %d, n, m) 2 (n || m)) { for (int i 1; i n; i) adj[i].clear(); memset(color, 0, sizeof(color)); for (int i 0; i m; i) { int a, b; scanf(%d %d, a, b); adj[a].push_back(b); adj[b].push_back(a); } bool ok true; for (int i 1; i n ok; i) { if (color[i] 0) { if (!bfs(i)) ok false; } } puts(ok ? YES : NO); } return 0; }几个值得注意的实现细节while (scanf(%d %d, n, m) 2 (n || m))是标准的读多组数据写法以n 和 m 同时为 0作为结束标记。如果题面只给单组数据把循环改成单次即可每组数据开始前必须先adj[i].clear()和memset(color, 0, sizeof(color))否则上一组数据残留的边和颜色会污染下一组主循环里一旦 bfs 返回 false就用 ok短路退出省得继续做无用功如果题目要求输出染色方案而不是仅输出 YES/NO只需要把最后的输出改成打印color[1]到color[n]或者遇到冲突时打印 -1。3.2 边界用例自测清单提交前建议先跑一遍这些用例能覆盖这个题 90% 的坑用例图结构预期输出检查目的单点图1 个顶点、0 条边YES空图也能染色两点一边1-2YES最小合法图三角形1-2、2-3、1-3NO奇数环反例四边形环1-2、2-3、3-4、4-1YES偶数环合法自环1-1NO自己和自己相邻必然冲突两个独立分量1-2、3-4两组无交叉边YES验证外层遍历每个连通分量两三角形拼接1-2、2-3、1-3、3-4、4-5、3-5NO奇环藏在复杂结构中BFS 也要能发现自环和重边的处理要看题面约定。多数题目默认没有自环和重边但如果没写明最好让代码对这两种情况保持鲁棒自环用染色逻辑天然判为 NO重边退化为普通边不影响结果。3.3 一次典型调试复盘说说我自己那次调试经历。第一版我用递归 DFS小样例全过一提交就段错误。排查后发现测试数据里构造了一条很长很长的链递归深度超过系统栈上限直接崩了。改成迭代 BFS 之后段错误消失但依然 WA。后来和同机房的同学一起对着代码逐行查才发现问题出在主循环我当时只在 1 号顶点上调用了一次bfs(1)没有遍历其他连通分量。两个问题都修掉之后这道题才真正过了。那次之后我总结了一条经验图论题的样例通常特别善良单连通、小规模、编号从 1 开始但后台数据专门挑不连通、超长链、极端编号这些场景下手。提交前先自己在草稿纸上把单点、无连通、长链、奇环四个用例跑一遍能省下至少两三次无谓的提交。4. 常见问题与排查心得4.1 高频报错速查表把新手常见的错误整理成一张表方便快速对号入座现象根本原因解决办法样例过了但 WA没有对每个连通分量启动染色外层循环遍历所有未染色顶点提交 RE 或段错误递归 DFS 栈溢出 / 邻接矩阵爆内存换 BFS用邻接表输出和预期完全相反没看清题面是输出 YES/NO 还是输出方案仔细读 Output 部分多组数据只有第一组正确color 和邻接表没有清空每组开始前重置大数据超时用了 O(N²) 判定确认是 BFS 染色O(NM)所有输出都是 YES建图时只加了一条方向的边无向图必须双向加边最后一行是重灾区。无向图的邻接表如果只在adj[a].push_back(b)而忘了adj[b].push_back(a)图就变成了有向图很多本该冲突的边不会被反向检查到于是所有答案都是 YES。遇到全 YES这种诡异现象第一个要怀疑的就是建图少了反向边。4.2 隐藏很深的三个细节第一个细节是节点编号起点。有的题目顶点从 1 开始有的从 0 开始数组开多一个位置没关系但循环边界必须跟着题面走。如果题面从 0 开始外层循环就写成for (int i 0; i n; i)建图时数组下标也和顶点编号对齐。第二个细节是输出格式。有些题要求YES有的要求Yes还有的只要Y或N。不要自己凭感觉敲把样例输出的格式原样复制到代码里最稳妥。这个细节和算法无关但就是能让人多交几发 WA。第三个细节是内存清理。memset(color, 0, sizeof(color))只对 color 数组有效邻接表必须逐个clear。如果只做了前者忘了后者上一组数据的边会残留在 vector 里导致这组数据多出一堆假边结果全错。写多组输入的题目时这两步最好放在一起做。5. 题外话二分图判定的工程价值5.1 真实场景里哪里在用刷题的时候容易觉得二分图判定是个纯考试概念其实不是。无线网络频点规划就是最直观的例子移动通信网络里相邻基站如果使用同一个频点覆盖重叠区的信号会互相干扰。工程上做小区的频点分配第一步就是检查邻区关系图能不能二染色能染就用两个频点把干扰问题彻底绕开不能染就得引入第三个频点或调整功率。你在这道 OJ 题里写的 BFS 染色放大到几千个小区、几万条邻区关系的规模上依然是核心算法骨架。类似的场景还有任务调度的冲突消解两个任务不能同时占用同一资源时判断能否分成两个时间段排课问题两个班不能共用同一教室时判断能否分成两天甚至社交网络里好友关系图的一些社区发现算法也把二分图判定当作基础组件。算法题和工程实践之间的距离往往比想象中近得多。5.2 学完这道题还能往哪个方向走这道题本身是二分图判定的入门款。沿着这条线往下可以解锁一串相关的经典问题带权并查集版本同样是判断两种关系的冲突但用并查集维护相对关系复杂度相近写法完全不同二分图最大匹配判定完之后如果想求最多能配多少对就进入匈牙利算法的领域奇环与图的二分性判定奇数环的存在性、统计奇环数量等延伸题也大多从染色法出发三染色与图着色推广从两种颜色推广到 k 种颜色问题的难度会急剧上升k 染色判定是著名的 NP 困难问题这也是为什么两种颜色这个条件如此重要。我个人建议的顺序是先把 BFS 染色写到闭眼能默写的程度再去看带权并查集的做法两相对比能帮你把关系传递想透彻。匈牙利算法可以等接触二分图匹配题时再配着学不必一次铺太开。最后再分享一点个人体会。这类披着应用场景外衣的基础图论题最忌讳的就是被题面牵着鼻子走。我现在读题有个习惯读完先不动手在草稿纸上把实体→顶点、关系→边、约束→颜色规则的映射写出来再决定用什么算法。无线广播这道题灵魂就在两种通道和相邻必须不同这两个条件里翻译成图论语言之后剩下的就是一遍 BFS 的事。把这个读题习惯练成肌肉记忆以后再遇到什么社交距离航班冲突染色问题一眼就能看到本质。