Hopcroft-Karp

Wiki › Thuật toán › Luồng mạng (Network Flow)

huunguyen · Last updated 8, Tháng 4, 2026, 15:54

Hopcroft-Karp là thuật toán tìm maximum bipartite matching trong $O (E \sqrt{V})$ , nhanh hơn đáng kể so với Hungarian $O (V E)$ cho đồ thị dày.

Ý tưởng

Thay vì tìm từng augmenting path một (Hungarian), Hopcroft-Karp tìm tập augmenting path ngắn nhất có thể (shortest augmenting paths) trong mỗi pha bằng BFS, rồi augment tất cả chúng song song bằng DFS.

Số pha: $O (\sqrt{V})$ — vì sau $\sqrt{V}$ pha đầu, matching còn thiếu tối đa $\sqrt{V}$ cạnh, mỗi lần augment tốn $O (E)$ .

Cài đặt

const int INF = 1e9;
const int MAXN = 2e5 + 5;

int n_left, n_right;
vector<int> adj[MAXN];   // adj[u]: danh sách đỉnh bên R kề u (bên L)

int match_l[MAXN];   // match_l[u] = đỉnh bên R ghép với u (-1 nếu chưa ghép)
int match_r[MAXN];   // match_r[v] = đỉnh bên L ghép với v (-1 nếu chưa ghép)
int dist_l[MAXN];    // khoảng cách BFS từ free vertex bên L đến u

bool bfs() {
    queue<int> q;
    for (int u = 1; u <= n_left; u++) {
        if (match_l[u] == -1) {
            dist_l[u] = 0;
            q.push(u);
        } else {
            dist_l[u] = INF;
        }
    }

    bool found = false;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            int w = match_r[v];
            if (w == -1) {
                found = true;
            } else if (dist_l[w] == INF) {
                dist_l[w] = dist_l[u] + 1;
                q.push(w);
            }
        }
    }
    return found;
}

bool dfs(int u) {
    for (int v : adj[u]) {
        int w = match_r[v];
        if (w == -1 || (dist_l[w] == dist_l[u] + 1 && dfs(w))) {
            match_l[u] = v;
            match_r[v] = u;
            return true;
        }
    }
    dist_l[u] = INF;   // ngăn đi lại trong pha này
    return false;
}

int hopcroft_karp() {
    fill(match_l + 1, match_l + n_left + 1, -1);
    fill(match_r + 1, match_r + n_right + 1, -1);

    int matching = 0;
    while (bfs()) {
        for (int u = 1; u <= n_left; u++)
            if (match_l[u] == -1 && dfs(u))
                matching++;
    }
    return matching;
}

Ví dụ sử dụng

int main() {
    cin >> n_left >> n_right;
    int m; cin >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
    }
    cout << hopcroft_karp() << "\n";
}

So sánh với Hungarian

	Hungarian	Hopcroft-Karp
Độ phức tạp	$O (V E)$	$O (E \sqrt{V})$
Cài đặt	Đơn giản	Phức tạp hơn
Khi nào nhanh hơn	Đồ thị thưa, $V$ nhỏ	Đồ thị dày, $V$ lớn

Thực tế: Với $n = 10^{3}$ , $m = 10^{5}$ : Hungarian $\approx 10^{8}$ ops, Hopcroft-Karp $\approx 3 \times 10^{6}$ ops.

Khi nào dùng Hopcroft-Karp?

Bài toán ghép cặp hai phía với $n, m$ lớn ( $n \geq 10^{3}$ , $m \geq 10^{5}$ ).
Khi Hungarian TLE.
Ghép cặp trọng số tối đa (kết hợp với min cost flow).

Bình luận

Không có bình luận tại thời điểm này.