图论算法：匈牙利算法

什么是二分图最大匹配？

• 二分图: 一个图的顶点可以被分为两个独立的集合 U 和 V，使得所有的边都连接 U 和 V 中的顶点，而 U 或 V 内部没有边。
• 匹配: 图中的一个边的集合，其中任意两条边都没有公共的顶点。
• 最大匹配: 一个图中，包含边数最多的匹配。

二分图最大匹配问题就是要在二分图中找到一个边数最多的匹配。这个问题在任务分配、资源调度等场景中有广泛应用。

匈牙利算法的核心思想

匈牙利算法是一种基于 增广路 (Augmenting Path) 的算法。

• 增广路: 一条在图中的路径，其起始点和终点都是未匹配的顶点，并且路径上的边是“未匹配边”和“已匹配边”交替出现的。

增广路定理: 一个匹配是最大匹配，当且仅当图中不存在增广路。

匈牙利算法的核心思想就是不断地在图中寻找增广路。每找到一条增广路，我们就可以沿着这条路，将路径上的“未匹配边”变为“已匹配边”，将“已匹配边”变为“未匹配边”。这个操作被称为 路径取反。

路径取反后，新的匹配中边的数量会比原来多一条。因此，我们只需要持续寻找增广路并进行路径取反，直到图中再也找不到增广路为止。此时，得到的匹配就是最大匹配。

算法流程

算法通常对左边的集合 U 中的每个顶点 u 进行一次尝试：

1. 初始化所有顶点为未匹配状态。
2. 遍历 U 中的每一个顶点 u： a. 为 u 寻找一条增广路。这通常通过一次深度优先搜索 (DFS) 或广度优先搜索 (BFS) 来实现。 b. 在一次为 u 寻找增广路的过程中，为了防止重复访问，需要一个 visited 数组。 c. DFS 过程 find_path(curr_u): i. 遍历 curr_u 的所有邻居 v。 ii. 如果 v 在本次为 u 的查找中未被访问过： - 标记 v 为已访问。 - 如果 v 是一个未匹配的顶点，或者 v 已经匹配了，但从 v 的匹配对象 match[v] 出发能找到一条增广路（即 find_path(match[v]) 为真），那么我们就找到了一条从 curr_u 开始的增广路。 - 此时，更新匹配关系 match[v] = curr_u，并返回 true。 d. 如果为 u 找到了增广路，则总匹配数加一。

C++ 伪代码

vector<int> adj[MAX_U];
int match[MAX_V];
bool visited[MAX_U];
int u_size, v_size;

bool dfs(int u) {
    for (int v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;
            if (match[v] < 0 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int hungarian() {
    int result = 0;
    memset(match, -1, sizeof(match));
    for (int u = 0; u < u_size; ++u) {
        memset(visited, 0, sizeof(visited));
        if (dfs(u)) {
            result++;
        }
    }
    return result;
}

匈牙利算法虽然名字听起来很复杂，但其核心的增广路思想相对直观，是解决二分图匹配问题的经典方法。