从事竞赛算法和软件开发这些年我陆续处理过不少看起来八竿子打不着的实际问题——考试排课、棋盘覆盖、任务分组、社交网络关系分析——最后发现它们的核心居然都指向同一个图论结构二分图。两年前带新人做团队项目时遇到一个典型场景要把一批课程安排到互不冲突的时间段当时我用了染色法做二分图判定十几行代码解决了一个原本靠人力反复试错的问题。从那以后我就认定二分图不是教科书里供着的抽象概念而是手边常备的一把螺丝刀。这篇文章把二分图的判定原理和简单应用彻底讲透。内容主要面向三类人正在学图论和算法的学生、准备面试需要练手题的开发者、以及在业务里遇到“分组/配对/冲突检测”类问题但还没意识到可以用二分图解决的工程朋友。读完你会发现判定二分图的核心工具是染色法而应用它的关键则在于把实际问题翻译成图、把图的约束翻译成两组节点的“内部无连边”条件。1. 先搞懂二分图到底在描述什么1.1 一组抽象定义和一个人人都懂的类比二分图的定义非常直白一个无向图 (G(V,E))如果能把它所有的顶点分成两个互不相交的集合 (A) 和 (B)使得图中每一条边的两个端点分别落在 (A) 和 (B) 里——换句话说集合内部没有边——那么这个图就是二分图。这个定义听起来有点干巴我一般会用“男生女生跳舞”来类比假设一场舞会上男生只和女生跳舞女生只和男生跳舞把男生看成图的一类顶点、女生看成另一类顶点每一次“共舞”就是一条连接男生和女生的边。那么“所有人能正常配对跳舞”这件事等价于整个关系网络是二分图。当然现实生活更复杂但这个类比几乎把所有二分图的关键性质都带出来了——同类节点之间没有直接连接关系。还有一个说法在竞赛圈更常用二分图等价于“没有奇环的图”。奇环就是指长度为奇数3、5、7……的环。为什么等价因为在一个二分图里从一个顶点出发沿着边走每走一步就跨到另一侧走奇数步必然到达颜色相反的一侧不可能走回起点反过来说如果一个图存在奇环你绕着环走一圈颜色肯定发生矛盾。所以“能否用两种颜色给所有顶点染色使得相邻顶点颜色不同”就成了判定二分图的最直接手段。1.2 为什么这个结构值得单独拿出来研究二分图之所以重要不只是因为它定义优雅而是因为大量真实问题只要落在二分图这个框架里就可以方便地利用它的强结构性质第一图上若干复杂约束可以简化。很多“不能把某些东西放在一起”的问题本质都是要把顶点分成两组组内关系全部切断。比如排课问题中同一时段不能安排同一个学生选修的两门课只要把课程作为顶点、冲突关系作为边判定这个图能否二分就等价于能不能把课程塞进两个时段。第二二分图上有成熟的高效算法。匹配问题就是典型代表最大匹配Hopcroft-Karp算法、最小点覆盖、最大独立集等一系列问题在二分图上都有多项式复杂度的漂亮解法但在一般图上却难得多。正因为二分图的结构足够“简单”才有这么多可用的理论支撑。第三它是图着色问题的一个特例。图着色问题是NP难的但“用两种颜色给图着色”这个特殊情形却非常简单用DFS或BFS线性时间就能判定。这个反差本身很有意思多一种颜色多出来的难度是爆炸性的。所以当你拿到一个问题如果发现它本质是“二选一分组”“配对”“冲突检测”第一反应就应该是我能不能把它削成一个无向图再做个二分判定。判定结果是“是”后续的匹配、覆盖、分配策略都能顺势套进去判定结果是“否”也说明这个问题至少需要三个时段或三组分配本身就是很有价值的结论。2. 染色法二分图判定的标准套路2.1 染色法背后的想法染色法的核心思想就一句话沿着边给顶点按顺序涂两种颜色每一条边的两个端点颜色必须相反。实际操作时我们从任意一个顶点开始给它涂颜色1然后把所有和它相邻的顶点涂成颜色2再把这些顶点的邻居涂回颜色1……如此交替传播。为什么这个方法一定能正确判定关键是考虑图不连通的情况。图不连通时各个连通分量互不影响所以需要依次遍历所有连通分量每个分量单独做染色。若整个图连通从起点出发的“染色洪流”会扫遍所有顶点如果这个过程顺利完成、每条边的两端颜色都相反显然图是二分图。一旦在某个顶点的邻接表里发现已经涂过颜色且颜色与当前需要的颜色相同就说明这里出现了一个奇数环直接返回不可行。这个想法的本质是给“二分图”定义加了一个可操作的判定流程测试能否成功执行“二染色”。去掉证明外壳后它不过是用遍历的方式把图的拓扑结构显式地摊开检查一遍。时间复杂度 (O(nm))一次DFS或BFS就能完成这就是二分图判定能被广泛用在各种在线场景里的底气所在。2.2 DFS染色——最经典、最容易写错的版本DFS版本是最容易理解的写法。下面这个模板我在很多场合都直接复用现在简单讲解一下。假设输入的图用邻接表存储数组color中0表示未染色1和2分别表示两种颜色#include cstring #include iostream #include vector using namespace std; const int MAXN 10005; int color[MAXN]; vectorint G[MAXN]; bool dfs(int u, int c) { color[u] c; for (int v : G[u]) { if (color[v] c) return false; // 相邻点撞色直接失败 if (color[v] 0) { // 尚未染色 if (!dfs(v, 3 - c)) return false; // 3-c 实现颜色切换 } } return true; } bool isBipartite(int n) { for (int i 1; i n; i) { if (color[i] 0) { if (!dfs(i, 1)) return false; // 处理不连通分量 } } return true; } int main() { int n, m; cin n m; for (int i 0; i m; i) { int u, v; cin u v; G[u].push_back(v); G[v].push_back(u); } memset(color, 0, sizeof(color)); puts(isBipartite(n) ? Yes : No); return 0; }这段代码里最需要留意的地方是3 - c这个技巧。当目前颜色是1时3 - 1 2得到相反的第二种颜色当目前颜色是2时3 - 2 1又切回来。这是一个很经典的“二值翻转”手法写熟练后自然理解但初学者常常会直接写成c 1当颜色值是2时就变成3了低级且致命。另一个容易被忽略的点是主函数里对每个未染色顶点循环启动DFS。这对应的是图不连通的情况一个满了的图拆成两个或多个互不相干的连通分量后每个分量内部仍然必须各自满足二分性质。漏掉这一步程序多半在第二组数据上就出问题。2.3 BFS染色——迭代版与两种写法的对比DFS版本写起来顺手但有一个隐患如果图的深度很大递归可能栈溢出。所以很多实际工程和面试中我用BFS迭代版本作为兜底。BFS的思路更接近“洪泛”直觉——用队列一层一层往外扩散每次入队时就把颜色定好#include cstring #include iostream #include queue #include vector using namespace std; const int MAXN 10005; int color[MAXN]; vectorint G[MAXN]; bool bfs(int s) { queueint q; q.push(s); color[s] 1; while (!q.empty()) { int u q.front(); q.pop(); for (int v : G[u]) { if (color[v] 0) { color[v] 3 - color[u]; q.push(v); } else if (color[v] color[u]) { return false; } } } return true; } bool isBipartite(int n) { memset(color, 0, sizeof(color)); for (int i 1; i n; i) { if (color[i] 0) { if (!bfs(i)) return false; } } return true; }BFS写法的优势在于不会递归爆栈而且天然是层序扩散对“染色传播过程”的观察更直观。DFS的好处是代码短、写起来快在很多在线评测或面试白板场景里更省时间。两者复杂度一样都是 (O(nm))。面试里我喜欢先写DFS如果面试官追问栈溢出风险再展示BFS版顺便把两种遍历的差异讲清楚这个节奏通常比较加分。说到空间占用邻接表存边是 (O(nm))颜色数组是 (O(n))所以整体空间开销也是线性的。这个特性让染色法可以很轻松地跑在百万顶点级别的图上如果一个题目号称点数巨大还要求二分判定基本就是用它没跑了。3. 简单应用一把二分的判定用到“冲突检测”里3.1 一个实战场景课程与考试安排每年期末考试周前教务老师最头疼的问题就是如何把多门考试塞进尽量少的考场和时段使得不会出现一个学生同一时段要考两门课的情况。把这个问题抽象出来已知若干课程的编号以及一个“冲突表”表里记录了哪些课同时被同一位学生选了所以不能放在同一时段。最少需要几个时段才能无冲突安排全部考试呢这个问题的特殊版本——当限定最多两个时段时——就是一个二分图判定问题。我把每门课程看成顶点两门课有冲突看成一条边那么“两个时段”就是两个颜色不存在同一时段冲突等价于所有边的两端颜色不同等价于这个冲突图是二分图。所以一段DFS染色代码就能搞定“能否用两个时段排完全部考试”这个判断。实际比赛和面试题里这类题的包装千变万化——有时是“拼餐桌”有时是“分实验室”但本质永远是这个给你若干对互斥元素问能否把它们分成两组让任意互斥对都分居两组。识别出这个结构后剩下的就只是读数据、建邻接表、跑染色。3.2 代码实现和判定结果怎么用下面给一个完整的“冲突检测”核心流程。注意这里的关键是如果染色成功我们不仅能回答“能不能”还能顺带输出每个元素应该分到哪一组。这在实际业务场景里非常实用因为你要的不仅是判断更是具体的安排方案。// 返回分组结果ans[v] 1 或 2 bool bipartition(int n, vectorint ans) { vectorint color(n 1, 0); bool ok true; for (int i 1; i n ok; i) { if (color[i] 0) { ok dfs(i, 1, color); // 同上模板DFS染色 } } if (ok) ans color; return ok; }如果返回true那ans数组就给出了具体分组返回false说明至少需要三个时间段。进一步地如果你想知道最少到底需要几个时段那就是图着色问题了——对一般图来说这是NP难的复杂度很高但因为这里是冲突检测场景顶点数通常不多可以考虑暴力回溯。但至少“二分判定”已经在最关键的分岔口给了你一个快速的低成本答案。我在一次实际去重排课的脚本里就用过这个思路先把课程冲突表建图用上面这个函数验证“两个时段够不够用”不够的时候再用启发式搜索把课拆到多个时段。实测时判断耗时在毫秒级这比起手工分时段的效率提升是肉眼可见的。你可以直接把这个函数抄进自己的项目替换掉手写判断的逻辑。4. 简单应用二棋盘覆盖问题里的黑白染色4.1 从棋盘到图再从图回到棋盘另一个经典应用是“棋盘覆盖”问题给定一个 (8 \times 8) 的国际象棋棋盘拿掉两个格子后问能否用若干个 (1 \times 2) 的多米诺骨牌完美覆盖剩下的所有格子。这个问题在初看时跟二分图八竿子打不着但它恰恰是最能体现二分图建模价值的启蒙题。先把棋盘按照国际象棋的棋格颜色染色——黑白相间。一块 (1 \times 2) 骨牌无论怎么放恰好覆盖一个黑格和一个白格。于是棋盘上的每个格子看成顶点相邻上下左右的格子之间连边整个棋盘就构成一个天然的二分图黑格是一个集合白格是另一个集合所有边都在黑白之间。到这里问题已经变成一个二分图的匹配问题能否找到一组边骨牌让每个顶点恰好被一条边覆盖即完美匹配问题。这里面最有意思的地方是判断的必要条件和充分条件之间的区分。完美匹配存在的必要条件是黑白格子数量相等这个条件用染色分分钟就能验证。但数量相等不保证一定存在覆盖方案——如果棋盘被挖了两个洞即使黑白数量恰好相等也可能无解。比如挖掉同色的两个角黑白数量就不等了直接判无解而挖掉恰好在颜色上平衡的两个格子则需要实际跑一遍匹配算法才能确定。这种“先做快速判定再做精细匹配”的分层思路在工程里也经常用到。4.2 小规模情况下的判定代码和边界讨论如果棋盘规模不大你可以先把格子编号为 (1) 到 (64)挖掉某些格子然后按相邻关系建图最后跑二分图匹配。匹配的部分不在这篇的讨论范围我先把建模和判定的代码给出来#include cstring #include iostream #include vector using namespace std; int n 8; bool removed[9][9]; int id[9][9]; vectorint G[65]; bool validateRemoval() { int black 0, white 0; for (int i 1; i n; i) for (int j 1; j n; j) { if (removed[i][j]) continue; if ((i j) % 2 0) black; else white; } return black white; } void buildGraph() { int cnt 0; for (int i 1; i n; i) for (int j 1; j n; j) { id[i][j] (removed[i][j] ? -1 : cnt); } const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; for (int i 1; i n; i) for (int j 1; j n; j) { if (removed[i][j]) continue; for (int k 0; k 4; k) { int ni i dx[k], nj j dy[k]; if (ni 1 || ni n || nj 1 || nj n || removed[ni][nj]) continue; G[id[i][j]].push_back(id[ni][nj]); } } }这个建模过程值得反复琢磨因为它展示了一个通用的“问题转化”方法论把空间邻接关系抽象为图上的边把使用一个单元件覆盖两个相邻空间的问题抽象为匹配问题。很多看似完全不相关的物理棋盘问题平移、旋转、变角度后都能落到这个框架里。需要注意的是这个应用如果延伸到一个更大的方向——比如任意一个棋盘挖掉两个同色格子后的覆盖判断逻辑、以及“所有骨牌覆盖方案本质上对应二分图的完美匹配集合”这一点——就已经很接近二分图匹配的核心内容了。对于“简单应用”这个定位先把黑白染色和数量判定吃透后续再深入匹配算法时你会有种一切水到渠成的感觉。5. 常见问题与排查技巧实录5.1 图不连通时的遍历起点这个问题在上面模板里其实已经规避过但我见过太多人栽在这里。如果你只从一个起点开始染色而另一个连通分量完全独立程序就会漏掉那个分量里的冲突边返回错误的“Yes”。特别是有些题面会把多组测试样例压在一起不连通就很容易混过去了。所以再次强调每一道二分图判定题都要对每个未染色的顶点做一次独立的DFS/BFS启动。5.2 递归栈溢出怎么办DFS写起来爽但图一旦是一条大链子深度可达几十万递归调用必然爆栈。我平时有两种应对方式换BFS版本或者用显式栈模拟DFS。前面列的BFS迭代版是我在实际落库时常用的方案因为它不用额外维护复杂的递归状态。另外在Linux环境里可以用编译选项增大栈空间例如ulimit -s unlimited或编译时附加特定参数但在评测系统上不保证有效所以最稳妥的做法还是写迭代版本。5.3 重边和自环对判定的影响重边不会影响染色结果因为“多条边”和“一条边”表达的是同样的约束——两个点不能同色只要有一条边就能判定矛盾重复的边并不会改变结果。但自环是必须警惕的一个顶点有一条连向自己的边这在二分图里就是一条两端同色的边必然返回“No”。如果你的建图逻辑里可能引入自环比如给某个课程登记了两次与自身的冲突务必在建图时过滤掉u v的情况否则程序会给出错误的二分判定结果。5.4 数据范围与存储选择顶点数到几万时邻接矩阵是绝对不能用的因为 (O(n^2)) 的空间会直接内存爆炸。我见过不少新人在做这类题时习惯用二维数组一旦顶点数超过5000就疯狂超空间。标准做法是邻接表vectorint G[MAXN]或者链式前向星这在面试和竞赛里都是默认选择。如果边数特别密集也可以考虑用bitset来优化空间和部分操作不过在二分判定这个层面朴素邻接表已经够用了。5.5 调试时的常用自检方法写完之后怎么快速验证程序是否正确我有一套固定的自检套路构造一个三角形三节点三次方预期输出“No”因为这是最小的奇数环构造一个正方形四节点四次方预期输出“Yes”因为偶数环是二分图构造一条长度为5的链预期输出“Yes”构造一个带孤立点的图比如一个点连着另一个点再加一个完全孤立的点预期输出“Yes”验证不连通处理正常构造一个六边形加一条对角线预期输出取决于对角线两端是否同色可以手动算一遍再对答案。用这个五个小例子基本能覆盖掉大多数实现的低级错误。我在写任何图论模板时都会先跑一遍这套自检确定代码本身可信了再往业务代码里集成。6. 从判定出发二分图应用能往哪里走我个人做算法题有一个习惯学会一个新结构后一定要把它放在整个知识体系里过一遍搞清楚相邻的扩展方向。二分图判定的下游正好躺着几个非常有价值的扩展点。判定的直接延伸是二分图匹配。匈牙利算法在竞赛题里是高频考点它解决的是“最多能配多少对”的问题应用场景包括任务分配、相亲配对、网格配对等。霍普克洛夫特-卡普算法则是二分图最大匹配的进阶算法在面对大图时能拿到更好的复杂度。再往下还有“最大点覆盖最大匹配”柯尼希定理、“最大独立集顶点数-最大匹配”这些直观且好用的公式它们让二分图在很多优化题目里成了核心解题模型。另一个扩展方向是判定本身在着色问题中的应用。图着色问题要求用尽量少的颜色给顶点着色、保证相邻顶点颜色不同而二分图判定就是“颜色数不超过2”时的特例。很多竞赛题会先问“能否用2种颜色”再问“能否用3种颜色”后者如果不能高效解决就说明题目可能是在考验搜索剪枝能力。学会判断“问题的颜色数”和“图本身的二分性”之间的关系对读题和解题思路的建立很有帮助。在实际工程里我个人还在依赖关系分析中用二分图做过分层——比如一个项目里的模块加载依赖如果依赖图是二分图就能把模块清晰地分成两个阶段并行构建并互不依赖。这种方法虽然没有匹配算法那种耳目一新的效果但简单、直观、稳定适合快速评估系统结构。所以在你的解题工具箱里这个判定模板真的应该当成压舱石一样的存在它简单到可以随时手写重要到能带出一整条图论应用链。一旦你对染色法的理解够深后面学匹配、学覆盖、学更高级的图结构都会顺畅得多。下次再遇到“能不能给这些东西分成两组”的问题别急着套业务逻辑先建个图跑一遍染色大概率会有意想不到的收获。