Masalah matching muncul ketika kita harus memasangkan elemen dari dua himpunan tanpa konflik: pekerja ke pekerjaan, mahasiswa ke asrama, atau item ke pembeli. Untuk graph bipartit, ada tiga algoritma klasik dengan trade-off yang berbeda: Kuhn’s algorithm (augmenting path DFS, sederhana, O(V·E)), Hopcroft-Karp (BFS layering + DFS, O(E·√V)), dan Hungarian algorithm (weighted assignment, O(n³)). Pada Chapter ini kita membedah dua algoritma pertama secara penuh dengan kode C++ yang dapat diuji, lalu menutup dengan ringkasan Hungarian untuk masalah weighted assignment. Pemilihan algoritma bergantung pada ukuran graph dan apakah edge memiliki bobot.

Aturan: Bipartite Matching #

Diberikan graph bipartit G = (L ∪ R, E) dengan L ∩ R = ∅. Sebuah matching adalah subset M ⊆ E sehingga setiap node muncul paling banyak satu kali di M. Maximum matching adalah matching dengan kardinalitas terbesar.

Beberapa istilah kunci:

IstilahDefinisi
Matched nodeNode yang menjadi endpoint suatu edge di M
Free nodeNode yang tidak matched
Alternating pathPath yang edge-nya bergantian di M dan tidak di M
Augmenting pathAlternating path dari free node ke free node
Perfect matchingSemua node matched; `

Theorem (Berge): Sebuah matching M maksimum iff tidak ada augmenting path terhadap M. Algoritma augmenting path memanfaatkan ini: cari augmenting path, lalu augment (toggle keanggotaan edge) untuk menambah |M| sebesar satu.

Mekanisme: Augmenting Path (Kuhn’s Algorithm) #

Kuhn’s algorithm melakukan iterasi untuk setiap node u ∈ L:

  1. Inisialisasi match_R[v] = -1 untuk semua v ∈ R (tidak ada yang matched).
  2. Untuk setiap u ∈ L: jalankan DFS dari u untuk mencari augmenting path ke free node di R.
  3. Saat DFS menemukan free node v di R, atau node v yang matched ke u' dan rekursi dari u' menemukan free node baru, augment dengan menetapkan match_R[v] = u.
  4. Flag used mencegah DFS mengunjungi u yang sama dua kali dalam satu iterasi (mencegah infinite loop pada cycle bipartit).

Setiap iterasi berhasil menambah |M| sebesar satu atau menandai u sebagai dead (tidak bisa match). Total O(V·E) karena setiap DFS O(E) dan ada O(V) iterasi.

Kode: Kuhn’s Algorithm (Augmenting Path) #

cpp 
#include <iostream>
#include <vector>

using namespace std;

class BipartiteMatching {
public:
    BipartiteMatching(int n_left, int n_right)
        : n_left_(n_left), n_right_(n_right), adj_(n_left) {}

    void add_edge(int u, int v) {
        adj_[u].push_back(v);
    }

    // DFS mencari augmenting path dari u.
    bool try_kuhn(int u, vector<char>& used, vector<int>& match_r) {
        if (used[u]) return false;
        used[u] = 1;
        for (int v : adj_[u]) {
            if (match_r[v] == -1 || try_kuhn(match_r[v], used, match_r)) {
                match_r[v] = u;
                return true;
            }
        }
        return false;
    }

    // Mengembalikan daftar pasangan (u, v) yang matched.
    vector<pair<int,int>> max_matching() {
        vector<int> match_r(n_right_, -1);
        int size = 0;
        for (int u = 0; u < n_left_; ++u) {
            vector<char> used(n_left_, 0);
            if (try_kuhn(u, used, match_r)) ++size;
        }
        vector<pair<int,int>> result;
        for (int v = 0; v < n_right_; ++v) {
            if (match_r[v] != -1) result.push_back({match_r[v], v});
        }
        result_size_ = size;
        return result;
    }

    int size() const { return result_size_; }

private:
    int n_left_, n_right_, result_size_ = 0;
    vector<vector<int>> adj_;
};

int main() {
    // L = {0,1,2,3}, R = {0,1,2,3}
    BipartiteMatching bm(4, 4);
    // Edges:
    // 0 -> 0,1
    // 1 -> 0,2
    // 2 -> 1,3
    // 3 -> 2
    bm.add_edge(0, 0); bm.add_edge(0, 1);
    bm.add_edge(1, 0); bm.add_edge(1, 2);
    bm.add_edge(2, 1); bm.add_edge(2, 3);
    bm.add_edge(3, 2);

    auto m = bm.max_matching();
    cout << "Ukuran matching maksimum: " << bm.size() << '\n';
    cout << "Pasangan (u, v):\n";
    for (auto [u, v] : m) {
        cout << "  L" << u << " -- R" << v << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Ukuran matching maksimum: 4
Pasangan (u, v):
  L1 -- R0
  L0 -- R1
  L3 -- R2
  L2 -- R3

Bedah Kode Baris-per-Baris #

  1. adj_(n_left): adjacency list dari kiri ke kanan. Graph bipartit direpresentasikan satu arah karena algoritma hanya travers dari L ke R lalu kembali ke L via match_r.
  2. add_edge(u, v): tambahkan edge u → v. Edge otomatis dianggap tidak berarah dalam konteks matching.
  3. try_kuhn(u, used, match_r): DFS rekursif. Basis: jika u sudah pernah dikunjungi di iterasi ini (used[u] == 1), kembalikan false untuk mencegah loop.
  4. for (int v : adj_[u]): coba setiap kandidat v di R. Dua kemungkinan: match_r[v] == -1 (free, augment), atau match_r[v] = u' dan DFS rekursif dari u' menemukan jalan ke free node lain (augment dengan re-routing u').
  5. match_r[v] = u: augment berhasil — node v sekarang matched ke u. Return true.
  6. vector<char> used(n_left_, 0): di-reset untuk setiap u baru. Tipe char (bukan bool) sedikit lebih efisien karena vector<bool> di-pack bit-by-bit.
  7. for (int u = 0; u < n_left_; ++u): proses setiap node kiri. Order matters — algoritma greedy dengan urutan input; hasil akhir sama-sama maksimum, tetapi pasangan spesifik bisa berbeda.
  8. Verifikasi: 4 pasangan (0,1), (1,0), (2,3), (3,2) semuanya valid (edge ada) dan semua node matched. |M| = 4 = |L| = |R| → perfect matching.

Mekanisme: Hopcroft-Karp (BFS Layering + DFS) #

Kuhn’s algorithm mencari satu augmenting path per iterasi. Hopcroft-Karp memproses banyak augmenting path sekaligus per fase:

  1. BFS layering: dari semua free node di L, bangun layer jarak terpendek ke free node di R melalui alternating path. Hanya edge yang menjaga jarak minimal yang dipakai.
  2. DFS augmenting: jalankan DFS paralel dari semua free node di layer 0. Setiap DFS mengikuti edge ke layer berikutnya; augment bila menemukan free node di R.
  3. Setelah satu fase selesai, ulang BFS — bila tidak ada augmenting path, berhenti.

Setiap fase menambah |M| sebesar jumlah augmenting path yang ditemukan; jarak augmenting path terpendek monoton naik tiap fase. Karena jarak maksimal O(√V), jumlah fase O(√V); setiap fase O(E). Total O(E·√V) — jauh lebih cepat untuk graph besar.

Kode: Hopcroft-Karp #

cpp 
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class HopcroftKarp {
public:
    HopcroftKarp(int n_left, int n_right)
        : n_left_(n_left), n_right_(n_right), adj_(n_left),
          match_l_(n_left, -1), match_r_(n_right, -1), dist_(n_left) {}

    void add_edge(int u, int v) { adj_[u].push_back(v); }

    int max_matching() {
        int size = 0;
        while (bfs()) {
            for (int u = 0; u < n_left_; ++u) {
                if (match_l_[u] == -1 && dfs(u)) ++size;
            }
        }
        return size;
    }

    vector<pair<int,int>> pairs() {
        vector<pair<int,int>> r;
        for (int u = 0; u < n_left_; ++u)
            if (match_l_[u] != -1) r.push_back({u, match_l_[u]});
        return r;
    }

private:
    bool bfs() {
        queue<int> q;
        bool found = false;
        for (int u = 0; u < n_left_; ++u) {
            if (match_l_[u] == -1) { dist_[u] = 0; q.push(u); }
            else                   dist_[u] = -1;
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj_[u]) {
                int u2 = match_r_[v];
                if (u2 != -1 && dist_[u2] == -1) {
                    dist_[u2] = dist_[u] + 1;
                    q.push(u2);
                } else if (u2 == -1) {
                    found = true;  // ada augmenting path di layer ini
                }
            }
        }
        return found;
    }

    bool dfs(int u) {
        for (int v : adj_[u]) {
            int u2 = match_r_[v];
            if (u2 == -1 || (dist_[u2] == dist_[u] + 1 && dfs(u2))) {
                match_l_[u] = v;
                match_r_[v] = u;
                return true;
            }
        }
        dist_[u] = -1;  // tandai u sebagai dead untuk fase ini
        return false;
    }

    int n_left_, n_right_;
    vector<vector<int>> adj_;
    vector<int> match_l_, match_r_, dist_;
};

int main() {
    HopcroftKarp hk(4, 4);
    hk.add_edge(0, 0); hk.add_edge(0, 1);
    hk.add_edge(1, 0); hk.add_edge(1, 2);
    hk.add_edge(2, 1); hk.add_edge(2, 3);
    hk.add_edge(3, 2);

    int sz = hk.max_matching();
    cout << "Hopcroft-Karp max matching: " << sz << '\n';
    cout << "Pasangan (u, v):\n";
    for (auto [u, v] : hk.pairs()) {
        cout << "  L" << u << " -- R" << v << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Hopcroft-Karp max matching: 4
Pasangan (u, v):
  L0 -- R1
  L1 -- R0
  L2 -- R3
  L3 -- R2

Bedah Kode Baris-per-Baris #

  1. match_l_ dan match_r_: tracking dua arah — match_l_[u] = v iff match_r_[v] = u. Mempermudah lookup dari kedua sisi. Berbeda dengan Kuhn yang hanya menyimpan match_r.
  2. bfs(): inisialisasi dist_[u] = 0 untuk semua free node u ∈ L (layer 0). Untuk setiap edge u → v:
    • Jika v free (match_r_[v] == -1): tandai found = true — ada augmenting path di fase ini.
    • Jika v matched ke u2 dan u2 belum dikunjungi: set dist_[u2] = dist_[u] + 1, push u2 ke queue (next layer).
  3. dfs(u): traverse hanya edge ke layer dist_[u] + 1. Bila v free atau u2 rekrusif menemukan augmenting path, augment dan return true.
  4. dist_[u] = -1 setelah DFS gagal: tandai u sebagai dead di fase ini, agar DFS paralel lain tidak mencoba lagi — inilah trik yang membuat setiap edge diproses O(1) per fase.
  5. while (bfs()): fase diulang selama masih ada augmenting path. Jarak augmenting path terpendek naik tiap fase, hingga O(√V) fase.
  6. Verifikasi: hasil sama dengan Kuhn — 4 pasangan perfect matching. Hopcroft-Karp menemukannya dalam 1-2 fase (tergantung urutan), bukan 4 iterasi seperti Kuhn.

Aplikasi: Assignment Problem #

Masalah assignment: n pekerja, n pekerjaan, matriks cost C[i][j]. Cari perfect matching dengan total cost minimum. Ini adalah weighted bipartite matching.

AlgoritmaKompleksitasUse case
Kuhn’s (augmenting path)O(V·E)Unweighted, sederhana
Hopcroft-KarpO(E·√V)Unweighted, graph besar
HungarianO(n³)Weighted (assignment problem)
Min cost max flowO(F·V·E)Weighted, dengan kapasitas

Hungarian algorithm mempertahankan potential u[i] untuk left dan v[j] untuk right sehingga u[i] + v[j] ≤ C[i][j] (dual feasible). Setiap iterasi menambah satu edge ke matching sambil menjaga dual feasibility — augmenting path + relabeling. Implementasi penuh memerlukan ~50 baris; untuk assignment problem dengan n ≤ 500, kode tersedia di banyak template kompetisi.

Kompleksitas dan Pemilihan #

AlgoritmaTimeSpaceCocok untuk
Brute forceO(n!)O(n)n ≤ 10
Kuhn’sO(V·E)O(V+E)Default, V ≤ 1000
Hopcroft-KarpO(E·√V)O(V+E)V ≥ 1000, dense graph
HungarianO(n³)O(n²)Weighted assignment
Min cost max flowO(F·V·E)O(V+E)Weighted, kapasitas

Ringkasan #

  • Bipartite matching: cari maximum subset edge tanpa konflik.
  • Augmenting path (Berge): matching maksimum iff tidak ada augmenting path.
  • Kuhn’s algorithm: DFS per node kiri, O(V·E), sederhana dan cepat untuk graph kecil.
  • Hopcroft-Karp: BFS layering + DFS paralel, O(E·√V), optimal untuk graph besar.
  • Hungarian algorithm: weighted bipartite matching O(n³), untuk masalah assignment.
  • Untuk skenario dengan cost dan kapasitas, reduksi ke min cost max flow (lihat Chapter network-flow).