C++匈牙利算法怎么求解二分图最大匹配-C++-PHP中文网

匈牙利算法的核心是不断寻找增广路径，每找到一条即可使匹配数加1；其本质是从未匹配左部点出发的交替路径，通过翻转路径上边的匹配状态来扩展匹配。

c++匈牙利算法怎么求解二分图最大匹配

匈牙利算法的核心是不断找增广路

它不直接“算匹配数”，而是通过反复尝试给未匹配左部点找一条能翻转边状态的路径（增广路），每找到一条，匹配数就+1。关键在于：每次 DFS 或 BFS 从一个未匹配的左部节点出发，只走“未匹配→已匹配→未匹配…”交替的边，且右部节点不能重复访问。

常见错误是没重置 visited 数组——每次从新左部点开始找增广路时，必须清空右部节点的访问标记；否则会漏掉本可扩展的路径。

左部点集合记为 U，右部点集合记为 V，邻接关系用 graph[u] 存储 u 能连到的 v 的列表
用 matchV[v] 记录右部点 v 当前匹配的左部点（-1 表示未匹配）
用 matchU[u] 记录左部点 u 当前匹配的右部点（-1 表示未匹配），可选，但查起来快
DFS 函数返回 bool：是否成功为当前 u 找到增广路

DFS 实现里怎么写递归逻辑

对当前左部点 u，遍历所有邻接右部点 v，若 v 未被本轮访问过，就标记并尝试：如果 v 没匹配，或 v 已匹配但其原配 matchV[v] 能腾出位置（即递归调用成功），就把 u 和 v 配上。

bool dfs(int u, const vector<vector>>& graph, vector<int>& matchV, vector<bool>& visited) {
    for (int v : graph[u]) {
        if (visited[v]) continue;
        visited[v] = true;
        if (matchV[v] == -1 || dfs(matchV[v], graph, matchV, visited)) {
            matchV[v] = u;
            return true;
        }
    }
    return false;
}</bool></int></vector>

注意：递归调用传的是 matchV[v]（即 v 原来的左部搭档），不是 u；这是让原配去另找对象，把位置“让”出来。

性能上，最坏时间复杂度是 O(V * E)，其中 V 是左部点数，E 是边数；实际中远快于理论值，尤其图稀疏时。