二分图最大匹配：匈牙利算法实现

2025-3-18

二分图最大匹配：匈牙利算法详解与实现

在图论中，二分图是一种特殊的图，其顶点可以被分成两个互不相交的独立集 U 和 V，并且图中的每条边都连接 U 中的一个顶点和 V 中的一个顶点。换句话说，同一集合内的顶点之间没有边相连。二分图匹配问题是寻找二分图中最大的边集合，使得集合中的任何两条边都不共享同一个顶点。这个问题在很多实际场景中都有应用，例如任务分配、人员匹配等。

匈牙利算法是一种经典的解决二分图最大匹配问题的算法，由匈牙利数学家 Edmonds 在 1965 年提出。该算法的核心思想是增广路径，通过不断寻找增广路径来增加匹配的边数，直到找不到增广路径为止。

本文将详细介绍匈牙利算法的原理、步骤、实现（包括 C++ 和 Python 代码示例），以及时间复杂度分析，并探讨一些实际应用场景。

1. 增广路径的概念

理解匈牙利算法的关键在于理解“增广路径”的概念。在二分图的匹配中，我们定义以下几种类型的顶点和路径：

  • 匹配点：已经属于匹配边的端点。
  • 非匹配点：尚未属于任何匹配边的端点。
  • 交错路径：一条路径，其边在匹配边和非匹配边之间交替出现。
  • 增广路径：一条特殊的交错路径，其起点和终点都是非匹配点。

增广路径有一个重要的性质：如果我们将增广路径上的匹配边和非匹配边互换，那么匹配的边数将会增加 1。这是因为增广路径的起点和终点都是非匹配点，路径上的边是匹配边和非匹配边交替出现，互换后，原本的非匹配边变成了匹配边，原本的匹配边变成了非匹配边，由于两端都是非匹配点，所以匹配边数加一。

举例说明：

假设有如下二分图（U 集：{u1, u2, u3, u4}，V 集：{v1, v2, v3, v4}）：

u1 -- v1
u2 -- v2
u3 -- v2
u4 -- v3

初始时，假设没有边被匹配。

  1. 我们从 u1 出发，找到一条路径 u1 -> v1。由于 u1 和 v1 都是非匹配点，这条路径是一条增广路径。将这条边加入匹配，匹配边数变为 1。

  2. 我们从 u2 出发，找到一条路径 u2 -> v2。由于 u2 和 v2 都是非匹配点，这条路径是一条增广路径。将这条边加入匹配，匹配边数变为 2。

  3. 我们从 u3 出发，找到路径 u3 -> v2。但 v2 已经是匹配点。我们继续从 v2 寻找，发现 v2 与 u2 匹配。我们沿着这条匹配边回溯到 u2。此时，我们找到一条交错路径 u3 -> v2 -> u2。但 u2 是匹配点，这条路径不是增广路径。

  4. 接着，u2 没有其他未访问的边，从u3访问 v2这一条路径失败。我们从 u3 出发尝试其他路径，没有找到增广路径。

  5. 我们从 u4 出发，找到一条路径 u4 -> v3。由于 u4 和 v3 都是非匹配点，这条路径是一条增广路径。将这条边加入匹配，匹配边数变为 3。

此时，我们找不到更多的增广路径，算法结束。最大匹配数为 3。

2. 匈牙利算法的步骤

基于增广路径的思想，匈牙利算法的主要步骤如下：

  1. 初始化：将所有顶点都视为非匹配点，初始匹配边集合为空。

  2. 寻找增广路径：从 U 集中的每个非匹配点 u 开始，尝试寻找一条以 u 为起点的增广路径。

    • 使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图。
    • 在遍历过程中，记录访问过的顶点和路径。
    • 如果找到一条以 u 为起点，以 V 集中的某个非匹配点 v 为终点的交错路径，则这条路径就是增广路径。

  3. 增广匹配：如果找到增广路径，则将路径上的匹配边和非匹配边互换，增加匹配的边数。

  4. 重复步骤 2 和 3：重复步骤 2 和 3，直到找不到任何增广路径为止。

  5. 返回最大匹配数：算法结束时，匹配边集合的大小即为最大匹配数。

3. 匈牙利算法的实现

下面分别给出匈牙利算法的 C++ 和 Python 代码实现。两种实现都使用了深度优先搜索（DFS）来寻找增广路径。

3.1 C++ 实现

```cpp

include

include

include

using namespace std;

const int MAXN = 505; // 最大顶点数

vector adj[MAXN]; // 邻接表存储图
int match[MAXN]; // match[v] 表示 V 集中的顶点 v 与 U 集中的哪个顶点匹配，-1 表示未匹配
bool visited[MAXN]; // 记录 V 集中的顶点是否被访问过

// 深度优先搜索寻找增广路径
bool dfs(int u, int n) {
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
if (match[v] == -1 || dfs(match[v], n)) {
match[v] = u;
return true; // 找到增广路径
}
}
}
return false; // 未找到增广路径
}

// 匈牙利算法
int hungarian(int n) {
int max_matching = 0;
memset(match, -1, sizeof(match));

for (int u = 1; u <= n; ++u) {
    memset(visited, false, sizeof(visited));
    if (dfs(u, n)) {
        max_matching++;
    }
}

return max_matching;

}

int main() {
int n, m, k; // n: U 集顶点数, m: V 集顶点数, k: 边数
cin >> n >> m >> k;

for (int i = 0; i < k; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v); // 只需从 U 集到 V 集建边
}

int max_matching = hungarian(n);
cout << "Maximum matching: " << max_matching << endl;

return 0;

}
```

3.2 Python 实现

```python
def dfs(u, adj, match, visited):
"""深度优先搜索寻找增广路径"""
for v in adj[u]:
if not visited[v]:
visited[v] = True
if match[v] == -1 or dfs(match[v], adj, match, visited):
match[v] = u
return True # 找到增广路径
return False # 未找到增广路径

def hungarian(n, adj):
"""匈牙利算法"""
max_matching = 0
match = [-1] * len(adj[0]) # match[v] 表示 V 集中的顶点 v 与 U 集中的哪个顶点匹配，-1 表示未匹配

for u in range(n):
    visited = [False] * len(adj[0])
    if dfs(u, adj, match, visited):
        max_matching += 1

return max_matching

if name == "main":
n, m, k = map(int, input().split()) # n: U 集顶点数, m: V 集顶点数, k: 边数

adj = [[] for _ in range(n)]
for _ in range(m):          #初始化足够长度，防止后面访问adj[u][v]时越界
    adj.append([])


for _ in range(k):
    u, v = map(int, input().split())
    u -= 1  # 将顶点编号转换为从 0 开始
    v -= 1
    adj[u].append(v)  # 只需从 U 集到 V 集建边

max_matching = hungarian(n, adj)
print("Maximum matching:", max_matching)

```

代码说明：

  • adj: 使用邻接表存储二分图，adj[u] 存储与 U 集顶点 u 相连的 V 集顶点列表。
  • match: match[v] 存储与 V 集顶点 v 匹配的 U 集顶点编号，-1 表示未匹配。
  • visited: 在 DFS 过程中，记录 V 集中的顶点是否被访问过，防止重复访问。
  • dfs(u, n) / dfs(u, adj, match, visited): 从 U 集顶点 u 开始进行深度优先搜索，尝试寻找增广路径。
    • 遍历与 u 相连的 V 集顶点 v。
    • 如果 v 未被访问过：
      • 标记 v 为已访问。
      • 如果 v 未匹配，或者从 match[v]（与 v 匹配的 U 集顶点）出发能找到增广路径，则将 v 与 u 匹配，并返回 True 表示找到增广路径。
    • 如果所有相邻的 V 集顶点都无法找到增广路径，则返回 False。
  • hungarian(n) / hungarian(n, adj): 匈牙利算法主函数。
    • 初始化 match 数组为 -1，表示所有顶点都未匹配。
    • 遍历 U 集中的每个顶点 u：
      • 重置 visited 数组为 False。
      • 调用 dfs(u, ...) 尝试寻找增广路径。
      • 如果找到增广路径，则最大匹配数加 1。
    • 返回最大匹配数。

输入格式：

两种实现都假设输入的第一行包含三个整数 n, m, k，分别表示 U 集顶点数、V 集顶点数和边数。接下来的 k 行，每行包含两个整数 u, v，表示 U 集中的顶点 u 和 V 集中的顶点 v 之间有一条边。

注意：

  • 在 C++ 实现中，顶点编号从 1 开始。
  • 在 Python 实现中，顶点编号从 0 开始（在输入时进行了转换）。
  • 两种实现都只建立了从 U 集到 V 集的边，因为在二分图中，我们只需要考虑从 U 集到 V 集的匹配。

4. 时间复杂度分析

匈牙利算法的时间复杂度取决于寻找增广路径的实现方式。

  • DFS 实现: 对于每个 U 集顶点，DFS 最多遍历所有顶点和边一次。因此，DFS 的时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。由于需要对每个 U 集顶点进行 DFS，所以总的时间复杂度为 O(U * (V + E))。在最坏情况下，U ≈ V ≈ V/2，E ≈ V^2，因此时间复杂度可以表示为 O(V * E)，更紧确地说是 O(min(U, V) * E)。
  • BFS 实现: BFS 的时间复杂度与 DFS 类似，也是 O(V + E)。总的时间复杂度也为 O(U * (V + E))，即 O(V * E)。

在实际应用中，匈牙利算法通常能够很快地找到最大匹配，尤其是在稀疏图中。

5. 实际应用场景

二分图最大匹配问题在许多实际场景中都有应用，以下是一些例子：

  • 任务分配：将一组任务分配给一组工人，每个工人只能完成特定的任务，每个任务也只能由特定的工人完成。可以将任务和工人分别看作二分图的两个顶点集，如果一个工人可以完成一个任务，则在它们之间连一条边。最大匹配就是找到一种分配方案，使得尽可能多的任务被完成。
  • 人员匹配：例如，在婚恋网站上，将男性和女性分别看作二分图的两个顶点集，如果两个人互相有好感，则在它们之间连一条边。最大匹配就是找到一种匹配方案，使得尽可能多的人能够配对成功。
  • 课程排课：将课程和时间段分别看作二分图的两个顶点集，如果一门课程可以在某个时间段上课，则在它们之间连一条边。最大匹配就是找到一种排课方案，使得尽可能多的课程被安排。
  • 网络流：最大二分匹配问题可以转化为最大流问题来解决。
  • 图像处理中的目标跟踪： 在多目标跟踪中，可以将前一帧的检测结果和当前帧的检测结果看作二分图的两部分，通过计算它们之间的相似度构建边。最大匹配可以用于找到最佳的匹配对，从而实现目标的跟踪。

6. 总结

匈牙利算法是一种高效解决二分图最大匹配问题的经典算法。其核心思想是增广路径，通过不断寻找增广路径来增加匹配的边数，直到找不到增广路径为止。本文详细介绍了匈牙利算法的原理、步骤、C++ 和 Python 代码实现、时间复杂度分析，以及一些实际应用场景。希望这篇文章能够帮助你深入理解二分图最大匹配问题和匈牙利算法。

版权声明：
作者：admin
链接：https://hostlocvps.com/2025/03/18/%e4%ba%8c%e5%88%86%e5%9b%be%e6%9c%80%e5%a4%a7%e5%8c%b9%e9%85%8d%ef%bc%9a%e5%8c%88%e7%89%99%e5%88%a9%e7%ae%97%e6%b3%95%e5%ae%9e%e7%8e%b0/
文章版权归作者所有，未经允许请勿转载。
THE END
Docker Hub官方文档解读：核心概念与操作指南
<<上一篇
如何利用Numpy GitHub提升你的数据分析技能
下一篇>>
相关推荐
用Grok APK分析竞争对手的Android应用
Matplotlib详解：自定义图表样式和属性
Verilog模块化设计实例分析
DuckDB和SQLite哪个好？完整比较与选择指南
正则表达式测试与调试：在线、即时、准确 (强调功能和优势)
如何利用Numpy GitHub提升你的数据分析技能
二分图最大匹配：匈牙利算法实现
Docker Hub官方文档解读：核心概念与操作指南
pgSQL (PostgreSQL) 数据库：优势、特点及与其他数据库比较
Kimi开放平台：API接口、功能与应用详解