01先把问题说具体
左侧学生 A、B,右侧项目 X、Y;A 可选 X 或 Y,B 只能选 X。先把 A 分给 X 后,怎样避免 B 无项目?
02一步步得到方法
最大匹配不能只做不回头的选择
匹配要求每个节点最多被选中一次。简单贪心 A→X 会卡住 B,但可将 A 改到 Y,释放 X 给 B。这个重新安排过程对应交替经过未匹配边与已匹配边的路径。
从尚未匹配的左节点出发,尝试一个右节点。若它空闲就成功;若已被另一个左节点占据,递归尝试给原拥有者另找位置,成功后把当前边接上。
每次增广只多一对
路径两端原先未匹配,内部节点一进一出。翻转路径上边的匹配状态后,原有内部节点仍各占一条边,而总匹配数增加 1。增广路定理说明不存在增广路时匹配已最大。
本课是二分图的 DFS 增广实现。一般图的最大匹配会遇到奇环,需要花算法等更复杂技术,不能直接套此程序。
增广路径让已有决定可以被重排
一个左侧点遇到已被占用的右侧点,不应立即放弃:若占用者能改配到另一个右侧点,就可以沿交替路径重新安排,让匹配总数增加1。
每次尝试增广都要有自己的访问标记,防止在同一次搜索中绕圈;下一次增广通常要允许重新访问,因为当前匹配已经改变。匹配数增加并不意味着所有旧配对都不变。
03把一个小例子完全算清楚
A 邻接 [X,Y],B 邻接 [X]。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 处理 A | 先匹配 A–X | 数量 1 |
| 处理 B | X 已被 A 占据 | 尝试重排 A |
| A 改到 Y | Y 空闲,成功 | 释放 X |
| B 接到 X | 匹配 B–X、A–Y | 数量 2 |
窄屏可左右滑动表格,阅读完整计算与理由。
回溯不是撤销已实现的数量,而是沿增广路重新分配。
04为什么这个方法成立
- match[v] 始终保存右节点唯一拥有者,保证右侧不重复。
- 递归成功才覆盖匹配,原拥有者已找到另一位置,因此左侧也不重复。
- 逐个尝试左节点的增广,最终不存在能增加数量的交替路径,得到最大匹配。
05把推导翻译成代码
Python · 可独立运行的教学实现
def maximum_matching(adj, right_count):
match = [-1]*right_count
def augment(u, seen):
for v in adj[u]:
if v in seen:
continue
seen.add(v)
if match[v] == -1 or augment(match[v], seen):
match[v] = u
return True
return False
count = 0
for u in range(len(adj)):
if augment(u, set()):
count += 1
return count, match逐个理解关键决定
augment(match[v], seen)- 先安置原拥有者,成功后才能接管这个右节点。
set()- 每次新的增广尝试重新创建访问集合;不同尝试不可共享永久 visited。
06时间、空间与实现范围
左侧 L 个节点,每次 DFS 至多扫描 O(E),总 O(LE),匹配与访问空间 O(L+R) 上界。
更大二分图可用 Hopcroft–Karp 的分层增广提升效率;本版本适合理解基本机制。
07改变条件,检查哪里会出错
遇到已匹配右节点就永久跳过
会错过可重新安排的增广路,如本例。
把一次搜索的 visited 永久复用
后续增广可能需要经过之前访问过的点,应按照实现的搜索轮次重置标记。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
左右都有 100 个节点,最大匹配至多多少?
需要一点提示
每对消耗两侧各一个。
查看解析与答案
至多 100,还可能受边约束更小。
两名学生都只选 X,能匹配几人?
需要一点提示
X 容量为 1。
查看解析与答案
1 人,换顺序只改变是谁,不能增加数量。
项目可收 3 人怎么扩展?
需要一点提示
右侧容量不再为 1。
查看解析与答案
小规模可复制三个槽位;更一般地建容量网络,用最大流表达项目容量。