专题进阶 · 图算法推荐总顺序 · 第 61 / 148 课

沿交替路径重新安排已匹配边,用增广提高配对数量。

先学会这些,再进入本课 二分图 深度优先搜索
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 图算法

最大匹配Maximum Matching

选择尽可能多且不共享端点的边;二分图可用增广路求解。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

沿交替路径重新安排已匹配边,用增广提高配对数量。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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
处理 BX 已被 A 占据尝试重排 A
A 改到 YY 空闲,成功释放 X
B 接到 X匹配 B–X、A–Y数量 2

窄屏可左右滑动表格,阅读完整计算与理由。

回溯不是撤销已实现的数量,而是沿增广路重新分配。

04为什么这个方法成立

  1. match[v] 始终保存右节点唯一拥有者,保证右侧不重复。
  2. 递归成功才覆盖匹配,原拥有者已找到另一位置,因此左侧也不重复。
  3. 逐个尝试左节点的增广,最终不存在能增加数量的交替路径,得到最大匹配。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

左右都有 100 个节点,最大匹配至多多少?

需要一点提示

每对消耗两侧各一个。

查看解析与答案

至多 100,还可能受边约束更小。

练习 2 · 边界与辨析

两名学生都只选 X,能匹配几人?

需要一点提示

X 容量为 1。

查看解析与答案

1 人,换顺序只改变是谁,不能增加数量。

练习 3 · 变式与迁移

项目可收 3 人怎么扩展?

需要一点提示

右侧容量不再为 1。

查看解析与答案

小规模可复制三个槽位;更一般地建容量网络,用最大流表达项目容量。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 图算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。