二部图判定原理与算法

可视化演示

二部图的顶点可分为两个集合且边只跨集合连接，等价于不含奇环。本文详解二部图的BFS与DFS染色判定方法、与无奇... 切换模式查看不同维度。

二部图定义

小A第一次拿到宾客名单时发现，只要把所有人分成“红帽组”和“蓝帽组”，并且保证每对互相认识的人都站在不同组，派对就能顺利开场。这个朴素想法正是二部图的核心：顶点可以被分成两个集合，所有边都只连接两个集合之间。

在数学上，一张无向图 \(G\) 是二部图，当且仅当它的顶点集 \(V\) 能被拆成两个互不相交的集合 \(X\) 和 \(Y\)，并且图中任意一条边的一个端点在 \(X\)，另一个端点在 \(Y\)。集合内部不允许出现边，这就是“组内无朋友、组间才有朋友”。

如果 \(X\) 中每个顶点都与 \(Y\) 中每个顶点相连，就得到完全二部图 \(K_{m,n}\)，它像两个阵营之间“全员加好友”的极端情况。理解定义后，下一步的关键问题就是：给定一张图，怎么快速判断它是不是二部图？

染色判定法

小A拿起帽子盒，从第一位嘉宾开始发帽子：他戴红帽，那么所有朋友都必须戴蓝帽，朋友的朋友再戴红帽……这个“波浪式发帽子”的过程，在图论里叫作染色。

BFS染色法用队列一层层传播颜色，DFS染色法则用递归沿着一条路走到黑再回头。两者本质相同：访问到一个未染色顶点时，给它染上“与邻居相反”的颜色；如果发现一条边两端已染色且颜色相同，就立刻判定该图不是二部图。因为此时这条边上的两个朋友被迫戴了同色帽，违反了规则。

无论从哪个顶点开始，只要全图能被两种颜色完成染色且无同色边，它就是二部图。BFS和DFS的复杂度都是 \(O(V+E)\)，相当于小A顺着朋友关系把所有帽子发一遍，每条朋友关系只检查一次，非常高效。

无奇环等价

小A很快发现一个规律：如果某个朋友圈恰好围成一个“三人铁三角”，红蓝帽子必定撞车；但四人围成的圈可以红蓝交替圆满解决。原因很简单——奇数长度的环无法完成二染色。

更一般地，一个图是二部图，当且仅当它不含奇数长度的环（简称奇环）。必要性很直观：奇环上从某个顶点出发走回自己，需要经过奇数条边，交替染色会让起点同时被要求戴两种颜色，矛盾。充分性则需要借助BFS分层：从起点出发按深度染色，令颜色等于深度对 2 取余；如果某条边连接两个同深度顶点，就说明存在奇环，否则染色成功。

所以小A不必真的把每条朋友关系都检查一遍，只要找到任何一处“奇数长度朋友圈”，就能断定这组嘉宾没法分成红蓝两队。这就是判定二部图的“捷径”定理。

匹配与增广

分出红蓝两组后，小A开始安排搭档游戏：每位嘉宾最多参加一次，搭档两人必须互相认识，他希望让尽可能多的人都玩上游戏。这个“一人最多一搭档”的边集合，就叫匹配。

匹配是图中一个边集，其中任意两条边不共享顶点。边数最多的匹配叫作最大匹配。如果当前匹配已经无法通过简单添加一条边来变大，还有办法吗？有——增广路径：一条从某个未匹配顶点出发，交替经过非匹配边、匹配边、非匹配边……最后停在另一个未匹配顶点上的路径。把这条路径上的匹配边和非匹配边互换，匹配数就会增加 1。

增广路径就像多米诺骨牌：一个人让位给新人，自己再去找下一位，一路传递下去，最终多凑出一组搭档。匈牙利算法正是利用这个思路，反复寻找增广路径直到找不到为止。

匈牙利算法

匈牙利算法是小A的“换搭档方案”：从每个还没有搭档的嘉宾出发，沿着好感关系尝试寻找增广路径；能找到就翻转路径让匹配数加 1，找不到就说明当前配对已经是最优。这个算法由匈牙利数学家 Edmonds 提出，因此得名。

算法用 DFS 实现最简洁。设左侧顶点集合为 \(X\)，右侧为 \(Y\)，用邻接表记录每个左侧顶点可选的右侧顶点。对每个左侧未匹配顶点 \(u\)，递归尝试其所有邻接顶点 \(v\)：若 \(v\) 未被访问且 \(v\) 未匹配，或能让 \(v\) 当前匹配的那个左侧顶点重新找到新搭档，就把 \(v\) 匹配给 \(u\)。整个过程本质上是在寻找一条增广路径，找到就沿路径取反。

找到增广路径后，把匹配边和非匹配边交换，记作 \(M \leftarrow M \oplus P\)，其中 \(\oplus\) 表示对称差。小A每次引入一个新嘉宾都想方设法“挤”进一组配对，最终所有人都无法再挤入时，就得到了最大匹配。

复杂度模板

小A发现，派对规模一大，“全场花名册”（邻接矩阵）会占很多内存，而“每人一张朋友名单”（邻接表）既省空间又方便遍历。匈牙利算法高效的关键，正是邻接表存储和递归 DFS 模板。

设左侧顶点数为 \(|X|\)，右侧顶点数为 \(|Y|\)，边数为 \(|E|\)。每个左侧顶点最多执行一次 DFS，每次递归会扫描与之相邻的边，因此时间复杂度是 \(O(|X|\cdot|E|)\)，通常简写为 \(O(VE)\)。空间上只存储邻接表和 match 数组，复杂度为 \(O(V+E)\)。在竞赛中，当点数在数百、边数在数万规模时，这个复杂度完全可行。

模板化的代码让小A可以快速套用：建图、跑匈牙利、输出匹配数。这也是算法竞赛和工程中最常见的“三板斧”。

实战应用

小A从派对中提炼出的方法，其实能解决大量现实问题：只要有“两类对象之间的偏好关系”，做一对一的资源分配，就可以建模成二部图最大匹配。先判断是否为二部图，再调用匈牙利算法求最大匹配，是一套通用解题框架。

在AI与工程场景中，二部图建模无处不在：任务分配把员工和任务当作两组顶点，偏好关系作为边；推荐系统把用户和候选物当作两组顶点；网络调度把请求和资源当作两组顶点。更妙的是，二部图还有一个重要性质——最小点覆盖大小等于最大匹配大小（Kőnig定理），这让我们能用匹配算法同时解决覆盖类问题。

小A的派对最终圆满成功：先分好红蓝两队，再配出最多的搭档组合。这套从“发帽子”到“牵线搭桥”的思路，正是二部图判定与匈牙利算法在真实世界中的价值所在。

AI 应用场景

Python 演示

# 匈牙利算法求二部图最大匹配def hungarian(match, visited, adj, u):    # 尝试为左侧顶点u寻找匹配,成功返回True    for v in adj[u]:        if visited[v]:            continue        visited[v] = True        if match[v] == -1 or hungarian(match, visited, adj, match[v]):            match[v] = u            return True    return False def max_matching(n_left, n_right, edges):    # 构建邻接表    adj = [[] for _ in range(n_left)]    for u, v in edges:        adj[u].append(v)    # match[v]记录右侧顶点v匹配的左侧顶点    match = [-1] * n_right    result = 0    for u in range(n_left):        visited = [False] * n_right        if hungarian(match, visited, adj, u):            result += 1    return result, match if __name__ == '__main__':    # 左侧3个顶点,右侧3个顶点,边表示愿意配对    edges = [(0, 0), (0, 1), (1, 1), (2, 0), (2, 2)]    ans, match = max_matching(3, 3, edges)    print("最大匹配数:", ans)    print("右侧匹配结果:", match)

1. def hungarian(match, visited, adj, u):定义递归函数，为左侧顶点 u 寻找增广路径。
2. for v in adj[u]:遍历与 u 有边相连的右侧顶点，相当于小A翻看嘉宾的好感名单。
3. if match[v] == -1 or hungarian(match, visited, adj, match[v]):若 v 空闲，或能让 v 当前搭档另寻出路，则尝试匹配。
4. match[v] = u记录右侧顶点 v 与左侧顶点 u 配对成功。
5. visited[v] = True每次递归都标记 v 已访问，避免在同一轮增广中反复占用同一右侧顶点。
6. for u in range(n_left):依次为每个左侧未匹配顶点尝试寻找增广路径。
7. visited = [False] * n_right每处理一个新的左侧顶点前，重置访问标记数组。
8. adj = [[] for _ in range(n_left)]用邻接表保存二部图，比邻接矩阵更省空间。

常见误区

面试题