图论算法：匈牙利算法原理解析 – wiki基地

作者： /

图论算法：匈牙利算法原理解析

图论作为计算机科学和数学中的重要分支，提供了强大的工具来建模和解决各种复杂问题。在图论中，匹配问题是一类非常经典且应用广泛的问题，它涉及在图的边中选取一个子集，使得选出的边之间没有共同的顶点。特别地，在二分图上寻找最大匹配或带权最佳匹配是许多实际应用（如任务分配、资源调度）的核心。而解决这类问题的经典算法之一，就是匈牙利算法 (Hungarian Algorithm)。

本文将深入探讨匈牙利算法的原理，主要聚焦于其解决无权二分图最大匹配问题的过程，并简要介绍其在带权二分图上的扩展（即常被称为Kuhn-Munkres算法的部分）。

1. 预备知识：二分图与匹配

在深入了解匈牙利算法之前，我们需要先明确一些图论的基本概念：

  • 图 (Graph)：由一组顶点 (Vertices) 和一组连接这些顶点的边 (Edges) 组成。通常表示为 G=(V, E)，其中 V 是顶点集合，E 是边集合。
  • 二分图 (Bipartite Graph)：一个图 G=(V, E) 如果其顶点集 V 可以被划分为两个互不相交的子集 U 和 V，使得 U ∪ V = V 且 U ∩ V = ∅，并且所有的边都连接着 U 中的一个顶点和 V 中的一个顶点，而 U 内部或 V 内部没有边，则称 G 是一个二分图。我们可以将其记为 G=(U ∪ V, E)。形象地说，二分图的顶点可以被“染成”两种颜色，使得同色顶点之间没有边。
  • 匹配 (Matching)：图 G 中的一个匹配是一个边的子集 M ⊆ E，满足 M 中任意两条边都没有公共的顶点。简单来说，就是选择一些边，这些边所连接的顶点都各不相同。
  • 最大匹配 (Maximum Matching)：一个图中包含边数最多的匹配。
  • 完美匹配 (Perfect Matching)：一个匹配 M，如果图 G 中的每个顶点都至少是 M 中某条边的端点（即所有顶点都被覆盖），则称 M 是一个完美匹配。完美匹配一定是最大匹配，但最大匹配不一定是完美匹配。只有当二分图的两个部分 U 和 V 大小相等 (|U| = |V|) 时，才可能存在完美匹配。
  • 交错路 (Alternating Path)：相对于某个匹配 M，一条路径如果其边在 M 中和不在 M 中交替出现，则称之为关于 M 的交错路。
  • 增广路 (Augmenting Path)：一条特殊的交错路，它起点和终点都是当前匹配 M 中的未匹配点 (Unmatched Vertex)。增广路是匈牙利算法的核心概念。

增广路为什么重要？考虑一条增广路 P。它的起点和终点是未匹配点。路径上的边交替属于 E \ M 和 M。由于起点和终点都是未匹配点，并且路径是交错的，这条路径上的 M 中的边比 E \ M 中的边少一条。如果我们“翻转”这条路径上的边的状态——将路径上属于 M 的边从 M 中移除，将路径上不属于 M 的边加入 M 中，会得到一个新的匹配 M’。M’ 的边数等于 M 的边数加上 1。这说明，只要存在增广路，当前匹配就不是最大匹配，可以通过找到增广路来增加匹配的大小。反之，如果不存在增广路，那么当前匹配就是最大匹配。这是匈牙利算法正确性的基础定理。

2. 无权二分图最大匹配：匈牙利算法的核心思想

基于“存在增广路当且仅当匹配不是最大匹配”的定理，匈牙利算法解决无权二分图最大匹配问题的基本思想是：

  1. 从一个空匹配开始。
  2. 重复地寻找一条相对于当前匹配的增广路。
  3. 如果找到增广路，则沿着增广路更新匹配，使匹配的边数增加 1。
  4. 重复步骤 2 和 3，直到找不到任何增广路为止。此时的匹配即为最大匹配。

算法的关键在于如何有效地寻找增广路。匈牙利算法采用了一种类似于深度优先搜索（DFS）或广度优先搜索（BFS）的方式来尝试为二分图左侧（U 部）的每一个未匹配点寻找一条增广路。

假设 U = {u₁, u₂, …, u_m}，V = {v₁, v₂, …, v_n}。算法的目标是找到一个最大的匹配 M。

3. 寻找增广路：深度优先搜索实现

我们通常从 U 部的顶点出发，尝试为每个未匹配的 U 部顶点寻找一个匹配对象。这个过程可以通过 DFS 来实现。

数据结构：

  • match[v]：一个数组，用于存储 V 部顶点 v 当前匹配的 U 部顶点编号。如果 v 未匹配，则 match[v] 为 -1 或其他标记值。初始化时所有 match[v] 都为 -1。
  • visited[u]：一个布尔数组，用于标记 U 部顶点 u 是否在当前这一轮寻找增广路的 DFS 过程中被访问过。这是为了避免在同一轮搜索中重复访问同一个 U 部顶点，防止死循环和提高效率。每次尝试为 U 部的一个新顶点寻找增广路时，都需要重置 visited 数组。

核心函数：find_augmenting_path(u) (尝试从 U 部顶点 u 出发寻找增广路)

这个函数使用 DFS 来尝试为 U 部顶点 u 找到一个匹配的 V 部顶点。

“`
function find_augmenting_path(u):
// 如果 u 在当前搜索路径中已经被访问过，则返回 false (避免循环)
if visited[u] is true:
return false

// 标记 u 在当前搜索路径中已被访问
visited[u] = true

// 遍历 u 的所有邻居 v (v 属于 V 部)
for each neighbor v of u:
    // 检查 v 是否未匹配，或者 v 已经匹配但它的原配可以通过递归调用找到新的匹配
    // match[v] == -1 表示 v 未匹配
    // find_augmenting_path(match[v]) 尝试为 v 的原配找到新的匹配
    if match[v] == -1 or find_augmenting_path(match[v]) is true:
        // 如果 v 未匹配，或者 v 的原配找到了新的匹配，则 u 可以与 v 匹配
        // 建立匹配关系：v 现在匹配 u
        match[v] = u
        // 找到了从 u 开始的一条增广路，返回 true
        return true

// 遍历完 u 的所有邻居，未能找到合适的匹配对象 (无法从 u 出发找到增广路)
return false

“`

主算法流程：

  1. 初始化 match 数组，所有元素置为 -1。
  2. 初始化匹配数 max_matching_size = 0。
  3. 遍历 U 部的每个顶点 i (从 0 到 |U|-1)：
    a. 重置 visited 数组，所有元素置为 false。这是因为每次尝试为新的未匹配 U 部顶点寻找增广路都是一个独立的搜索过程。
    b. 调用 find_augmenting_path(i)。
    c. 如果 find_augmenting_path(i) 返回 true，表示成功为顶点 i 找到了一个匹配对象，也就是找到了一条增广路。沿着这条增广路更新了匹配，匹配数增加 1。因此，将 max_matching_size 加 1。
  4. 遍历完所有 U 部顶点后，max_matching_size 即为二分图的最大匹配数。

算法执行过程的解释：

当 find_augmenting_path(u) 被调用时，它试图为 u 寻找一个匹配。它遍历 u 的邻居 v。
* 如果 v 是未匹配的 (match[v] == -1)，那么 u -- v 就是一条长度为 1 的增广路（从未匹配的 u 到未匹配的 v）。此时，我们将 u 和 v 匹配起来 (match[v] = u)，并返回 true，表示成功找到了一条增广路。
* 如果 v 已经匹配，例如 v 当前与 u' 匹配 (match[v] == u')，那么我们不能直接让 u 和 v 匹配，因为这会破坏 v 和 u' 的匹配。但是，我们可以尝试让 u' 放弃 v，去寻找一个新的匹配对象。这就需要递归调用 find_augmenting_path(u')。
* 如果 find_augmenting_path(u') 返回 true，意味着 u' 成功找到了一个新的匹配。此时，u' 不再需要 v，v 就“空闲”了出来。于是，u 可以与 v 匹配 (match[v] = u)。这样，我们就找到了一条增广路：u -- v -- u' -- (u' 的新匹配) ...。这条路从 u (未匹配) 开始，经过 v (当前在匹配中)，到 u' (当前在匹配中)，然后沿着 u' 找到的新匹配路径继续，最终达到一个新的未匹配点。由于 u' 成功找到了新匹配，这条路径的终点是一个未匹配点。整条路径是交错路，且起点和终点都是未匹配点，所以是增广路。在这种情况下，find_augmenting_path(u) 返回 true。
* 如果 find_augmenting_path(u') 返回 false，意味着 u' 无法找到新的匹配。在这种情况下，v 不能放弃 u' 来与 u 匹配，因为 u' 将无法匹配。因此，从 u 经过 v 这条路无法形成增广路。find_augmenting_path(u) 会继续尝试 u 的其他邻居。

如果在遍历完 u 的所有邻居后，都没有找到可以与之匹配的 V 部顶点（无论是未匹配的还是其原配能找到新匹配的），则 find_augmenting_path(u) 返回 false。这意味着从当前的匹配状态出发，顶点 u 无法作为增广路的起点。

每次主循环调用 find_augmenting_path(i) 并成功（返回 true），就找到了一条增广路并更新了匹配，匹配数加一。这个过程保证了每次匹配数都增加，直到找不到增广路，达到最大匹配。

4. 实例演示 (简化)

考虑一个简单的二分图，U = {u0, u1, u2}, V = {v0, v1, v2, v3}，边集 E = {(u0, v0), (u0, v1), (u1, v1), (u2, v2), (u2, v3)}。

初始匹配 M = {}，match = {-1, -1, -1, -1} (对应 v0, v1, v2, v3)。最大匹配数 count = 0。

  1. 处理 u0：

    • 重置 visited = {false, false, false} (对应 u0, u1, u2)。
    • 调用 find_augmenting_path(u0)。visited[u0] = true。
    • 检查 u0 的邻居 v0。v0 未匹配 (match[v0] == -1)。
    • 找到增广路 u0 — v0。match[v0] = u0。返回 true。
    • count 变为 1。当前匹配 M = {(u0, v0)}。match = {u0, -1, -1, -1}。

  2. 处理 u1：

    • 重置 visited = {false, false, false}。
    • 调用 find_augmenting_path(u1)。visited[u1] = true。
    • 检查 u1 的邻居 v1。v1 未匹配 (match[v1] == -1)。
    • 找到增广路 u1 — v1。match[v1] = u1。返回 true。
    • count 变为 2。当前匹配 M = {(u0, v0), (u1, v1)}。match = {u0, u1, -1, -1}。

  3. 处理 u2：

    • 重置 visited = {false, false, false}。
    • 调用 find_augmenting_path(u2)。visited[u2] = true。
    • 检查 u2 的邻居 v2。v2 未匹配 (match[v2] == -1)。
    • 找到增广路 u2 — v2。match[v2] = u2。返回 true。
    • count 变为 3。当前匹配 M = {(u0, v0), (u1, v1), (u2, v2)}。match = {u0, u1, u2, -1}。

所有 U 部顶点处理完毕。最大匹配数 count = 3。最大匹配可以是 {(u0, v0), (u1, v1), (u2, v2)}。

另一种情况的演示 (涉及递归):

假设边集为 E = {(u0, v0), (u1, v0), (u2, v1), (u2, v2)}。U={u0,u1,u2}, V={v0,v1,v2}。

  1. 处理 u0：找到增广路 u0 — v0。M = {(u0, v0)}。match={u0, -1, -1}。count=1。
  2. 处理 u1：重置 visited。find_augmenting_path(u1)。visited[u1]=true。
    • 检查 u1 的邻居 v0。v0 已匹配 (match[v0] == u0)。
    • 递归调用 find_augmenting_path(u0)。重置 本次递归调用中 的 visited 数组（例如，使用参数传递visited状态或复制一份）。visited[u0]=true。
    • 检查 u0 的邻居 v0。v0 是当前调用的起点 match[v0]，不能匹配自己。u0 没有其他邻居。find_augmenting_path(u0) 返回 false。
    • 回到 find_augmenting_path(u1)。u1 通过 v0 找不到增广路。u1 没有其他邻居。find_augmenting_path(u1) 返回 false。
    • count 仍为 1。
  3. 处理 u2：重置 visited。find_augmenting_path(u2)。visited[u2]=true。
    • 检查 u2 的邻居 v1。v1 未匹配 (match[v1] == -1)。
    • 找到增广路 u2 — v1。match[v1] = u2。返回 true。
    • count 变为 2。M = {(u0, v0), (u2, v1)}。match={u0, u2, -1}。

所有 U 部顶点处理完毕。最大匹配数 count = 2。最大匹配可以是 {(u0, v0), (u2, v1)} 或 {(u1, v0), (u2, v1)} 或 {(u1, v0), (u2, v2)} 等。匈牙利算法找到的是其中一个最大匹配。

5. 算法复杂度和正确性

正确性：

匈牙利算法的正确性基于增广路定理：当且仅当一个匹配是最大匹配时，图中不存在相对于该匹配的增广路。算法通过不断寻找增广路来增加匹配大小，直到找不到增广路为止，此时根据定理，当前匹配即为最大匹配。每次找到增广路都能使匹配数增加 1，因此算法最终会终止。

时间复杂度：

在使用 DFS 实现寻找增广路时：
* 外层循环遍历 U 部的每个顶点，共 |U| 次。
* 内层 find_augmenting_path 函数（DFS）在最坏情况下会探索整个图。一次 DFS 的时间复杂度是 O(|V| + |E|)，其中 |V| 是顶点数，|E| 是边数。在二分图中，顶点数 |V| = |U| + |V’| (这里用 V’ 区分 V 部集合和总顶点数)，边数是 |E|。
* 由于每次调用 find_augmenting_path 前都需要重置 visited 数组，并且 DFS 的探索路径可能重叠，但关键在于 visited 数组防止了在 同一次 DFS 搜索中重复访问 U 部顶点。一个 U 部顶点最多会在外层循环中作为起点被处理一次。在一次 find_augmenting_path(u) 调用中，每个邻居 v 的递归调用 find_augmenting_path(match[v]) 最多发生一次。整个 DFS 过程可以看作是在构建一个交错树/森林。
* 总的时间复杂度约为 O(|U| * (|V| + |E|))。在二分图中，通常 |V| 远小于 |E| 的数量级（除非图非常稀疏），且对于邻接矩阵表示法是 O(|V|^2)，对于邻接表表示法是 O(|V| + |E|)。因此，使用邻接表时，总复杂度更接近 O(|U| * |E|)。考虑到 |U| <= |V|，实际复杂度可以写为 O(|V| * |E|)。对于稠密图（E接近V^2），复杂度是 O(|V|^3)。使用 BFS 实现寻找增广路 (即 Hopcroft-Karp 算法) 可以将无权二分图最大匹配的复杂度优化到 O(E√V)，但在原理上，匈牙利算法更直观地体现了增广路的概念。

6. 匈牙利算法的扩展：带权二分图最佳匹配 (Kuhn-Munkres 算法)

匈牙利算法最初（由 Kuhn 提出，Munkres 改进）是用来解决带权二分图的最小权完美匹配问题的，这通常被称为 Kuhn-Munkres 算法 (KM 算法)。虽然名字相同，但这里的原理与上面讨论的无权图增广路方法有所不同，或者说，无权图的增广路方法可以看作 KM 算法在特定情况（权值都为 1 或 0）下的简化。

KM 算法的核心思想是利用顶标 (Vertex Labels/Potentials)将带权匹配问题转化为在特定子图（称为相等子图或可行边子图）中寻找完美匹配的问题。

  • 给 U 部的每个顶点 u 赋予一个顶标 lx[u]，给 V 部的每个顶点 v 赋予一个顶标 ly[v]。
  • 这些顶标必须满足条件：对于图中的任意一条边 (u, v)，其权值 weight(u, v) 必须小于等于 lx[u] + ly[v]。即 lx[u] + ly[v] >= weight(u, v)。
  • 相等子图 (Equality Subgraph)：包含原图所有顶点，以及那些满足 lx[u] + ly[v] == weight(u, v) 的边。
  • KM 算法的定理：如果相等子图中存在一个完美匹配，那么这个完美匹配就是原图中的一个权值之和最小的完美匹配。
  • 算法流程概要：
    1. 初始化顶标。例如，lx[u] 可以初始化为与 u 相连边的最大权值，ly[v] 初始化为 0。
    2. 在当前的相等子图中尝试寻找一个完美匹配（可以使用类似匈牙利算法的增广路方法，但搜索过程是在相等子图中进行）。
    3. 如果找到完美匹配，算法结束。
    4. 如果找不到完美匹配（意味着从某个 U 部顶点出发，在相等子图中找不到增广路），则通过修改顶标来“扩大”相等子图，使其包含更多的边，以便下一次搜索更容易找到完美匹配。顶标的修改方式是：对于搜索过程中访问过的 U 部顶点集合 S 和 V 部顶点集合 T (在相等子图中无法继续延伸的点)，计算一个最小的差值 delta = min(lx[u] + ly[v] - weight(u, v))，其中 u 属于 S 且 v 不属于 T (或者反之，具体取决于搜索方向)。然后将所有 S 中的 lx 值减去 delta，所有 T 中的 ly 值加上 delta。这个操作保证了新的顶标仍然满足 lx' + ly' >= weight 条件，并且至少有一条新的边 (原本满足 lx[u] + ly[v] - weight(u, v) == delta 的边) 被加入到新的相等子图中。
    5. 重复步骤 2-4，直到找到完美匹配。

KM 算法的复杂度通常是 O(|V|^3)，对于解决带权二分图最佳匹配问题非常有效。它是解决指派问题（Assignment Problem，一种特殊的带权二分图完美匹配问题）的经典方法。

7. 应用领域

匈牙利算法（及其 KM 扩展）在许多领域有广泛应用：

  • 任务分配/指派问题 (Assignment Problem)：将一组工人分配给一组任务，每个工人完成不同任务的效率或成本不同，目标是找到总效率最高或总成本最低的分配方案。
  • 资源调度：将有限资源分配给不同的需求方，以优化某些指标。
  • 计算机视觉：目标跟踪中的帧间匹配。
  • 模式识别：图像或图形的匹配与比较。
  • 生物信息学：DNA 或蛋白质序列的比对，分子结构匹配。
  • 排课系统：匹配学生和课程，或教师和课程。

8. 总结

匈牙利算法是解决二分图匹配问题的强大工具。对于无权二分图，其核心思想是基于增广路定理，通过不断寻找并利用增广路来增大匹配，直到无法找到增广路达到最大匹配。使用 DFS 实现寻找增广路是常见的做法，其时间复杂度为 O(|V| * |E|)。对于带权二分图的最佳匹配问题，其扩展——Kuhn-Munkres 算法，则通过调整顶标，在相等子图中寻找完美匹配来解决，原理更为复杂但同样优雅高效，通常用于解决指派问题。

掌握匈牙利算法对于理解图论在组合优化和算法设计中的应用至关重要。它不仅提供了解决特定问题的具体方法，更体现了通过迭代改进寻找最优解的普适性思想。

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注

滚动至顶部