跳到主要内容

匈牙利算法

一、直观理解：左右两边一对一配对，尽量多配成​

二分图 G=(L∪R,E)G=(L\cup R,E) 的顶点分成两个互不重叠的集合，边只出现在 LL 与 RR 之间。匹配是没有公共顶点的边集合。最大匹配是边数最多的匹配。

应用：

  • 工人—任务（每人一任务）；
  • 课程—教室时段；
  • 左侧用户—右侧物品的一对一分配。

匈牙利算法（Kuhn，1955；也常与 Kuhn–Munkres 的带权版本区分）用增广路反复扩大匹配：从匹配边与非匹配边交替走，若找到从未匹配左点到未匹配右点的增广路，则对称差后匹配数 +1。

Hall 婚配定理给出完美匹配存在的充要条件；算法则给出构造。

二、适用场景与优缺点​

类型说明
适用场景无权最大匹配；分配问题的可行性阶段；作为最大流建模对照。
核心优点正确性清晰；增广路思想可迁移；可手写教学；与流算法互通。
局限与缺点无权；带权最优分配需 KM/费用流；实现若用朴素 DFS 为 O(nm)O(n m)，大图需优化或改用 Hopcroft–Karp。

三、核心原理​

1. 增广路​

相对当前匹配 MM，交替路是非匹配边与匹配边交替出现的路径。两端都是自由点的交替路为增广路。沿增广路取对称差，∣M∣|M| 加一。

2. Berge 引理​

MM 最大 ⟺ 不存在增广路。

3. 算法框架（DFS/BFS 找增广）​

对每个未匹配左点尝试找增广路；用 pairU/pairV 记录匹配；DFS 中对右侧点尝试占用或“挤走”原匹配左点。

4. 与最大流​

源连所有左点，右点连汇，原边容量 1，最大流=最大匹配。

四、关键决策​

1. 是否需要完美匹配​

若 ∣M∣<∣L∣|M|<|L|，报告哪些左点无法分配，并检查图是否缺边。

2. 多重任务/容量​

右点可接多个时，改为容量 >1 的流，而非简单二分匹配。

3. 带权​

转 KM 或最小费用最大流。

4. 验证​

匹配边不共点；无法再增广；可用流结果对照。

五、MATLAB 示例​

% 左 1..nL, 右 1..nR
% 邻接：adj{u} = 右侧点列表
nL = 4; nR = 4;
adj = {
    [1 2]
    [1]
    [2 3]
    [3 4]
};

pairU = zeros(nL,1);
pairV = zeros(nR,1);

function ok = dfs(u, adj, pairU, pairV, vis)
    ok = false;
    for v = adj{u}
        if vis(v), continue; end
        vis(v) = true;
        if pairV(v)==0 || dfs(pairV(v), adj, pairU, pairV, vis)
            pairU(u) = v;
            pairV(v) = u;
            ok = true;
            return;
        end
    end
end

% 注意：MATLAB 嵌套需共享 vis；这里用循环多轮
match = 0;
for u = 1:nL
    vis = false(nR,1);
    % 重新实现为局部函数调用困难时用显式栈式 DFS
    % 下面用简单递归函数句柄 + 容器
end

% 用显式可运行版本：
pairU = zeros(nL,1); pairV = zeros(nR,1);
    function ok = dfs2(u)
        for vv = adj{u}
            if seen(vv), continue; end
            seen(vv) = true;
            if pairV(vv)==0 || dfs2(pairV(vv))
                pairU(u) = vv; pairV(vv) = u;
                ok = true; return;
            end
        end
        ok = false;
    end

for u = 1:nL
    if pairU(u)==0
        seen = false(nR,1);
        if dfs2(u)
            match = match + 1;
        end
    end
end

fprintf("最大匹配数 = %d\n", match);
for u = 1:nL
    if pairU(u)>0
        fprintf("L%d -- R%d\n", u, pairU(u));
    end
end

% 最大流对照
s = []; t = [];
% 节点编码: src=1, L:2..1+nL, R:2+nL..1+nL+nR, sink=2+nL+nR
src = 1; sink = 2+nL+nR;
for u = 1:nL
    s(end+1)=src; t(end+1)=1+u; %#ok<SAGROW>
    for v = adj{u}
        s(end+1)=1+u; t(end+1)=1+nL+v;
    end
end
for v = 1:nR
    s(end+1)=1+nL+v; t(end+1)=sink;
end
G = digraph(s, t, ones(size(s)));
mf = maxflow(G, src, sink);
fprintf("流网络最大匹配 = %g\n", mf);

六、如何解释结果​

  1. 左右集合含义；
  2. 匹配边列表与基数；
  3. 未匹配顶点及原因（缺邻接/结构障碍）；
  4. 若用于排班，给出可执行分配表；
  5. 算法与复杂度说明。

七、常见误区​

1. 贪心“先配度小的”当最优​

贪心不一定最大。

2. 有权问题仍用无权匈牙利​

目标错了。

3. 非二分图硬套​

一般图匹配更复杂（Blossom）。

4. 不检查一人多任务约束​

模型与业务不一致。

八、小结​

匈牙利算法（增广路法）的核心是：

反复寻找交替增广路，直到匹配最大。

它是二分图分配可行性的标准解，也是理解 KM、匹配与流之间联系的基础。结果应同时给出匹配表与不可分配对象的诊断。