二分图与匹配：两类对象之间的配对问题
讲解二分图染色、最大匹配、匈牙利算法直觉，以及任务分配、资源匹配等工程场景。
知识目录数据结构与算法：从基础到工程实践47 / 77
学“二分图与匹配：两类对象之间的配对问题”时，我走过的弯路可以概括成一句话：二分图匹配第一次学时，我只看到不断找增广路，没理解为什么一次重新匹配反而能让总匹配数增加。问题不在于知识点有多难，而在于我一开始只盯着结果，没有看到它在维护什么关系。下面是我重新补这块基础时留下的笔记。
二分图是一类特殊图：节点可以分成左右两组，边只连接左右两边，不连接同组内部。它非常适合表达“人和任务”“用户和商品”“学生和课程”这类两类对象之间的匹配关系。
二分图的结构
图：红线表示一个合法匹配，每个左点和右点最多使用一次
二分图常见问题：
- 判断一个图是否能二分。
- 求最大匹配。
- 判断是否存在完美匹配。
- 任务分配和资源分配。
判断二分图
如果一个图可以用两种颜色染色，并且每条边两端颜色不同，那么它就是二分图。
boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n];
for (int i = 0; i < n; i++) {
if (color[i] != 0) continue;
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(i);
color[i] = 1;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph[u]) {
if (color[v] == 0) {
color[v] = -color[u];
queue.offer(v);
} else if (color[v] == color[u]) {
return false;
}
}
}
}
return true;
}
最大匹配的直觉
最大匹配是选择尽可能多的边，要求每个点最多属于一条边。
匈牙利算法的核心是“让一让”：如果当前左点想匹配某个右点，而右点已经被占用，就尝试让原来的左点去找其他可选右点。
boolean dfs(int u, List<List<Integer>> graph, int[] matchRight, boolean[] seen) {
for (int v : graph.get(u)) {
if (seen[v]) continue;
seen[v] = true;
if (matchRight[v] == -1 || dfs(matchRight[v], graph, matchRight, seen)) {
matchRight[v] = u;
return true;
}
}
return false;
}
外层对每个左点尝试增广：
int maxMatching(List<List<Integer>> graph, int rightSize) {
int[] matchRight = new int[rightSize];
Arrays.fill(matchRight, -1);
int ans = 0;
for (int u = 0; u < graph.size(); u++) {
boolean[] seen = new boolean[rightSize];
if (dfs(u, graph, matchRight, seen)) ans++;
}
return ans;
}
工程场景
二分图匹配适合资源分配类问题：
- 面试官和候选人安排。
- 课程和教室分配。
- 用户和推荐位匹配。
- 订单和骑手匹配的简化模型。
- 测试用例和执行机器调度。
真实工程中还会有权重、容量和实时变化，这时可能需要最小费用最大流、启发式算法或业务规则系统。
我的分析
二分图最重要的是建模：左右两边分别是什么，边表示什么条件成立。只要建模清楚，后面才谈匹配算法。很多业务分配问题并不是纯二分图，因为一个资源可能有容量、优先级、距离、时间窗，这些都要额外建模。
面试题
- 如何判断一个图是不是二分图？
- 二分图为什么不能有奇数环？
- 最大匹配和完美匹配有什么区别？
- 匈牙利算法中的“增广”是什么意思？
- 二分图匹配在工程里会遇到哪些额外约束？
JARVIS · 当前文章
有哪里没看懂？可以只问这篇。
Jarvis 会限定在《二分图与匹配：两类对象之间的配对问题》及其公开关联内容中检索，并把引用定位回原文章节。