图的匹配与最大匹配算法

可视化演示

展示图匹配三大核心：二部图匹配、增广路径交替路、Kuhn-Munkres最优权匹配，通过动态网络图演示匹配过程。

匹配定义与性质

团建总导演的第一件事，是搞清楚什么叫「合格」的组队方案。假如同事之间有6条合作意愿边，你不可能全安排——因为每个员工分身乏术。合格的方案只能挑出一些边，保证「没有两条边共用同一个人」。这就是匹配的本质：从边集中挑出互不打架的边。

在数学上，图 \( G=(V,E) \) 的一个匹配 \( M \)，就是满足「任意两条边都没有公共端点」的边集。最大匹配是边数最多的匹配，完美匹配则是让每个顶点都被匹配边覆盖的匹配——相当于所有人都组上了队，一个不落。注意，不是所有图都有完美匹配，正如不是每次团建都能全员上阵。

$$\displaystyle M=\{e_1,e_2,\ldots,e_k\}\subseteq E,\qquad e_i\cap e_j=\varnothing\ (\forall i\neq j),\qquad |M|\le \left\lfloor\frac{|V|}{2}\right\rfloor$$

1. 边集选取：匹配 \( M \) 是从原图所有边中挑出的一个子集

$$\displaystyle M\subseteq E$$

2. 两两不相交：任意两条匹配边 \( e_i \) 与 \( e_j \) 没有公共端点，用交集为空表示

$$\displaystyle e_i\cap e_j=\varnothing$$

3. 边数上界：每条边消耗2个顶点，所以匹配边数最多是顶点数的一半

$$\displaystyle |M|\le \left\lfloor\frac{|V|}{2}\right\rfloor$$

回到团建：匹配是「每人只参与一队」的纪律，最大匹配是「在不违反纪律的前提下组出最多队伍」，而完美匹配是「全体成员都找到了队伍」。理解了这个基础，接下来要解决的关键问题就是：如何系统性地让队伍数量一步步逼近上限。

增广路径定理

现在的组队方案是 \( M \)（比如2队），你想再塞进一队，但所有人都已经被安排了。总导演的经验是：不要硬抢，试着让两对组合「串一串」。比如小张和小李搭档、小王和小赵搭档，如果小张其实更想和小赵搭档，小李又闲着没组上，就能形成一条「换人链」，让整体队伍数量+1。

这条「换人链」在数学上叫增广路径。它是一条路径，边在「非匹配边—匹配边—非匹配边—匹配边」之间交替出现，并且路径的两端都是未匹配顶点。沿着这条路径，把匹配边和非匹配边全部互换——也就是对路径做对称差运算——队伍数量就会增加1。图 \( G \) 的匹配 \( M \) 是最大匹配，当且仅当 \( G \) 中不存在关于 \( M \) 的增广路径。 这就是增广路径定理，整个最大匹配算法的理论基石。

$$\displaystyle M' = M \oplus P = (M\setminus P)\cup(P\setminus M),\qquad |M'|=|M|+1$$

1. 交替特征：路径上的边交替属于 \( M \) 与不属于 \( M \)，不能连续两条同为匹配边或同为非匹配边

$$\displaystyle P=(v_0,v_1,\ldots,v_t),\quad e_{2i}\notin M,\ e_{2i+1}\in M$$

2. 两端空闲：路径的起点 \( v_0 \) 与终点 \( v_t \) 都是未匹配顶点，这是「能新塞一队」的前提

$$\displaystyle v_0,v_t\notin V(M)$$

3. 对称差操作：把路径上的边全部「取反」——原来的匹配边变为非匹配边，非匹配边变为匹配边

$$\displaystyle M' = M \oplus P$$

4. 数量加一：路径上非匹配边比匹配边多一条，取反后匹配边总数净增1

$$\displaystyle |M'|=|M|+1$$

增广路径就像团建排班里的「连锁调整」：只要有人愿意调整搭档，就总能多组一队。而增广路径定理保证了这一策略的完备性——当所有连锁调整都尝试过仍无法新增队伍时，你手里的方案就是全局最优。那么具体如何系统性地找到增广路径呢？这就轮到匈牙利算法登场了。

匈牙利算法

匈牙利算法的思路，像一个「先到先得 + 及时让位」的排班系统。算法从左边的未匹配顶点出发，用深度优先搜索（DFS）或广度优先搜索（BFS）尝试寻找增广路径。每找到一个未匹配的右顶点，就尝试把它占下；如果这个右顶点已经被匹配，就递归地让它的搭档「再去找别的右顶点」，也就是腾位。

这个过程会形成一棵交替搜索树：树的根是未匹配左顶点，往下交替走「非匹配边—匹配边」。如果树中某个未匹配右顶点被探到，就说明找到了一条增广路径；此时沿路径做对称差更新匹配，匹配数+1。对每个左顶点重复这一过程，直到没有增广路径可找。因为每轮增广至少增加一条匹配边，而匹配数上界是 \( \lfloor n/2 \rfloor \)，加上DFS本身要遍历 \( O(E) \) 条边，总复杂度为 \( O(VE) \)。

$$\displaystyle \text{对每个未匹配 } u\in X:\ \text{DFS}(u)\ \text{找增广路径};\quad \text{找到则 } M\leftarrow M\oplus P$$

1. 逐一尝试：依次从每个未匹配的左顶点出发，把它当作搜索树的根

$$\displaystyle u\in X,\ u\notin V(M)$$

2. 递归腾位：DFS 访问右顶点 \( v \)，若 \( v \) 未匹配则找到增广路径；若已匹配给 \( u' \)，则递归让 \( u' \) 另寻他路

$$\displaystyle v\notin V(M)\Rightarrow \text{增广成功};\quad v\in V(M)\Rightarrow \text{DFS}(u')$$

3. 访问标记：每轮 DFS 维护 \( \text{visited} \)，避免重复搜索形成死循环

$$\displaystyle \text{visited}[v]=\text{true}$$

4. 匹配数增长：每找出一条增广路径，匹配边数加1，直到不存在增广路径

$$\displaystyle |M|\leftarrow |M|+1$$

匈牙利算法完美继承了增广路径定理的「体检报告」逻辑：每一轮要么找到增广路径让匹配更优，要么证明该顶点已无路可增广。它的局限也很明显——只适用于二部图，因为一旦图中有奇环（如三角形），递归可能陷入同一批顶点的循环。这个坑，要等Blossom算法来填。先把二部图问题彻底解决，我们再谈带权的最优匹配——KM算法。

KM最优匹配

团建总导演渐渐不满足于「队伍最多」——他开始关心总产出：每对搭档合作能创造不同的价值，他希望让总价值最大。这正是最优匹配（带权匹配）问题，Kuhn-Munkres算法（简称KM）是它的经典解法。KM算法的妙招是给每个顶点发一张「能力标价牌」，规则是左顶标 \( l(x) \) 加右顶标 \( l(y) \) 必须不低于两人合作的收益 \( w(x,y) \)，这叫可行顶标。

在所有边中，只保留「标价刚好等于收益」的边，这些边组成相等子图。可以证明：若相等子图中存在完备匹配，那么这个匹配一定是最优匹配，且总收益恰好等于所有顶标之和。如果当前相等子图找不到完备匹配，就适当降低某些左顶标、提高某些右顶标，让更多边进入相等子图，直到找到完备匹配为止。KM算法通过反复增广和调整顶标，保证在 \( O(n^3) \) 时间内得到最优解。

$$\displaystyle l(x)+l(y)\ge w(x,y),\quad \forall x\in X, y\in Y$$

$$\displaystyle \text{若 } G_l \text{ 有完备匹配 } M^*, \text{ 则 } \sum_{e\in M^*} w(e)=\sum_{x\in X}l(x)+\sum_{y\in Y}l(y)$$

1. 可行顶标：左顶点 \( x \) 与右顶点 \( y \) 的顶标之和不小于边权，保证顶标是「不虚高」的上界

$$\displaystyle l(x)+l(y)\ge w(x,y)$$

2. 相等子图：只保留满足 \( l(x)+l(y)=w(x,y) \) 的边

$$\displaystyle G_l=\{(x,y): l(x)+l(y)=w(x,y)\}$$

3. 完备匹配判定：在相等子图中寻找覆盖所有顶点的完美匹配

$$\displaystyle M^*\text{ 是 } G_l \text{ 的完备匹配}$$

4. 最优性证明：任意匹配 \( M \) 的总权不超过顶标总和，而 \( M^* \) 恰好达到该和

$$\displaystyle w(M)\le \sum l(v)=w(M^*)$$

KM算法的「标价牌」像相亲节目里的心动值：先给每个人打一个「理想分」，只撮合分数刚好互补的两人；撮合不齐时再微调分数，让更多候选者进入待选池。因为这套标价体系始终锁定了收益的上限，一旦凑齐完备配对，就同时拿到了「人数满员」和「收益最大」的双重最优。不过，无论是匈牙利还是KM，都默认图是二部图——如果同事之间的关系网出现「三角恋」式的奇环，又该怎么办？

Blossom奇环

当图不是二部图时，事情变得棘手。二部图里，每条交替路径从左部出发必然回到右部，永远「黑白分明」；而一般图中的奇环（比如三角形）会让交替搜索树从不同方向探到同一个顶点，迭代陷入死循环——就像团建排班时三个人互相盯上了对方搭档，怎么调整都出不来新方案。

Edmonds在1965年给出了天才解法：把奇环整体收缩成一个「花苞」（Blossom）。奇环内部无论怎么匹配，一定恰好剩一个未匹配顶点（因为奇环顶点数为奇数），所以收缩后用一个超级顶点代替整个环，继续在外层跑增广路径；一旦找到增广路径，再展开花苞、还原环内的匹配细节。这个过程叫开花算法，成功把一般图最大匹配拉回多项式时间。

$$\displaystyle G' = G/B,\qquad \nu(G)=\nu(G')+\left\lfloor\frac{|B|}{2}\right\rfloor$$

1. 奇环识别：交替搜索树中，若同一顶点被两条不同路径到达，且形成长度为奇数的环

$$\displaystyle B=(v_1,v_2,\ldots,v_{2k+1},v_1)\text{ 为奇环}$$

2. 收缩操作：将整个奇环压缩为一个超级顶点 \( b \)，环外部边全部连到 \( b \)

$$\displaystyle G' = G/B$$

3. 匹配数量守恒：环内部最多匹配 \( \lfloor |B|/2 \rfloor \) 对，收缩图与原图最大匹配数相差这个值

$$\displaystyle \nu(G)=\nu(G')+\left\lfloor\frac{|B|}{2}\right\rfloor$$

4. 展开还原：外部增广完成后，把超级顶点还原成环，并按交替规则补全内部匹配

$$\displaystyle B \text{ 展开},\quad |M\cap B|=\left\lfloor\frac{|B|}{2}\right\rfloor$$

Blossom算法相当于给总导演配了一个「矛盾仲裁器」：遇到三角纠结就暂时把这几个人看作一个整体单元，先解决外部大局；大局落定后再回到内部细抠。正是这个「收缩—搜索—展开」三部曲，让最大匹配从二部图扩展到任意图，理论基础由此完备。有了这套完整工具箱，我们终于可以回答最初的问题——这些算法能解决哪些真实世界的难题？

匹配应用场景

学完了四种「组队策略」，总导演身份直接切换成各行各业的「资源调度官」。最典型的场景是指派问题：有 \( n \) 个任务和 \( n \) 个人，第 \( i \) 个人做第 \( j \) 个任务需花费 \( c_{ij} \)，要让总成本最小。把任务和人分别看作二部图两侧顶点，成本看作边权，就跑一趟KM算法——这正是很多排班软件、物流配送系统的内核。

调度问题同样天然是匹配模型：云计算要把GPU设备分配给计算任务，直播平台要把转码任务调度到空闲服务器，本质都是在「任务—资源」二部图上求最大匹配或最优匹配。竞赛和算法题中也常见它的变体，比如棋盘覆盖问题：用「多米诺骨牌」覆盖棋盘上可用的格子，每块骨牌占相邻两格，求最多覆盖多少——把每个可用格子看成一个顶点，相邻关系看成边，最大匹配直接给出答案。

$$\displaystyle \min \sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}x_{ij},\qquad \text{s.t. } \sum_{i=1}^{n}x_{ij}=1,\ \sum_{j=1}^{n}x_{ij}=1,\ x_{ij}\in\{0,1\}$$

1. 决策变量：\( x_{ij}=1 \) 表示把任务 \( j \) 指派给人员 \( i \)，否则为0

$$\displaystyle x_{ij}\in\{0,1\}$$

2. 任务约束：每个任务恰好被一个人完成，所以每列求和为1

$$\displaystyle \sum_{i=1}^{n}x_{ij}=1$$

3. 人员约束：每个人恰好承担一个任务，所以每行求和为1

$$\displaystyle \sum_{j=1}^{n}x_{ij}=1$$

4. 目标函数：所有指派的总花费最小化

$$\displaystyle \min \sum_{i,j}c_{ij}x_{ij}$$

至此，从「如何定义合格组队」到「如何找最多队伍」，再到「如何让收益最大」和「如何处理三角恋死循环」，我们用团建组队这条主线把图匹配的整个知识版图走了一遍。这些算法并非纸上谈兵——它们正在无数调度系统中默默运行，帮人类在纷繁复杂的资源约束里寻找那个最优解。

AI 应用场景

Python 演示

def dfs(u, adj, match_r, seen):    for v in adj[u]:        if seen[v]:            continue        seen[v] = True        if match_r[v] == -1 or dfs(match_r[v], adj, match_r, seen):            match_r[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_r = [-1] * n_right    cnt = 0    for u in range(n_left):        seen = [False] * n_right        if dfs(u, adj, match_r, seen):            cnt += 1    return cnt, match_r def perfect_matching_exists(n_left, n_right, cnt):    if n_left != n_right:        return False    return cnt == n_left if __name__ == "__main__":    # 二部图: 左侧3个任务, 右侧3台机器    # 边表示任务u可以被机器v执行    edges = [        (0, 0), (0, 1),        (1, 1), (1, 2),        (2, 1), (2, 2),    ]    n = 3    cnt, match_r = max_matching(n, n, edges)    print("maximum matching size:", cnt)    for r, u in enumerate(match_r):        if u != -1:            print("task %d -> machine %d" % (u, r))    print("perfect matching exists:", perfect_matching_exists(n, n, cnt))

1. def dfs(u, adj, match_r, seen):递归搜索增广路径，u 是当前尝试匹配的左顶点，adj 是每个左顶点的可连右顶点列表
2. if match_r[v] == -1 or dfs(match_r[v], adj, match_r, seen):核心「让位」逻辑：若右顶点 v 空闲则直接占用；否则递归地让 v 当前的搭档另寻他路
3. match_r[v] = u腾位成功后，把右顶点 v 匹配给 u，匹配关系更新
4. for u in range(n_left):依次为每个左顶点寻找增广路径，每成功一次匹配数加1
5. seen = [False] * n_right每轮新搜索都重置访问标记，防止递归在同一轮内绕圈
6. cnt == n_left若匹配数等于左顶点数，说明所有任务都被分配，构成完美匹配

常见误区

面试题