最大二部マッチングとは？アルゴリズムとC++実装例をわかりやすく解説

最大二部マッチングとは

二部マッチング（bipartite matching）とは、グラフの中から辺の集合を選ぶ際に、選ばれたどの2つの辺も端点を共有しないようにする手法です。その中でも、最も多くの辺を選べるマッチングを最大マッチングと呼びます。

最大マッチングが求められた状態では、それ以上の辺を追加することはできません。仮に最大マッチング済みのグラフへ新たな辺を1本追加すると、その集合はもはやマッチングとして成立しなくなります。また、二部グラフでは最大マッチングが複数存在する場合もあります。

この問題は「応募者と求人の割り当て」といった形で、現実のマッチング問題によく例えられます。以下では、応募者M人と求人N件を題材に、最大マッチングを求めるアルゴリズムを紹介します。

入力と出力

入力には、応募者と求人の対応関係を表す隣接行列を使用します。

Input:
隣接行列
0 1 1 0 0 0
1 0 0 1 0 0
0 0 1 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 1

Output:
求職者と求人をマッチングできる最大人数: 5

アルゴリズム

bipartiteMatch(u, visited, assign)

入力：開始ノード、訪問状況を記録するvisitedリスト、ノード間の割り当てを管理するassignリスト。

出力：頂点uに対するマッチングが可能であればtrueを返します。

Begin
    for all vertex v, which are adjacent with u, do
        if v is not visited, then
            mark v as visited
            if v is not assigned, or bipartiteMatch(assign[v], visited, assign) is true, then
                assign[v] := u
                return true
    done
    return false
End

この関数は、応募者uが希望する求人vを順に確認し、まだ訪問していない求人であれば訪問済みとしてマークします。求人vが空いていればそのまま割り当てます。すでに他の応募者に割り当てられている場合は、その応募者に対して再帰的に別の求人を探し、移動先が見つかれば割り当てを組み替えてuに求人vを与えます。

maxMatch(graph)

入力：与えられたグラフ。

出力：マッチングの最大数。

Begin
    initially no vertex is assigned
    count := 0
    for all applicant u in M, do
        make all node as unvisited
        if bipartiteMatch(u, visited, assign), then
            increase count by 1
    done
End

maxMatch関数では、すべての応募者についてbipartiteMatchを呼び出し、マッチングが成功するたびにカウントを増やしていきます。各試行の前に訪問状態をリセットすることで、毎回新しい経路を探索できるようにしています。

C++による実装例

#include <iostream>
#define M 6
#define N 6
using namespace std;

bool bipartiteGraph[M][N] = {    // M人の応募者とN件の求人からなるグラフ
    {0, 1, 1, 0, 0, 0},
    {1, 0, 0, 1, 0, 0},
    {0, 0, 1, 0, 0, 0},
    {0, 0, 1, 1, 0, 0},
    {0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 1}
};

bool bipartiteMatch(int u, bool visited[], int assign[]) {
    for (int v = 0; v < N; v++) {    // すべての求人（0〜N-1）を確認
        if (bipartiteGraph[u][v] && !visited[v]) {    // 応募者uが希望し、未訪問の求人vの場合
            visited[v] = true;    // 求人vを訪問済みとしてマーク
            // vが未割り当て、または元の応募者が別の求人に移れる場合
            if (assign[v] < 0 || bipartiteMatch(assign[v], visited, assign)) {
                assign[v] = u;    // 応募者uに求人vを割り当てる
                return true;
            }
        }
    }
    return false;
}

int maxMatch() {
    int assign[N];    // どの求人がどの応募者に割り当てられたかを記録する配列
    for (int i = 0; i < N; i++)
        assign[i] = -1;    // 初期状態ではすべての求人が空き
    int jobCount = 0;

    for (int u = 0; u < M; u++) {    // すべての応募者について
        bool visited[N];
        for (int i = 0; i < N; i++)
            visited[i] = false;    // 初期状態ではどの求人も未訪問
        if (bipartiteMatch(u, visited, assign))    // 応募者uが就職できた場合
            jobCount++;
    }
    return jobCount;
}

int main() {
    cout << "Maximum number of applicants matching for job: " << maxMatch();
}

実行結果

Maximum number of applicants matching for job: 5

まとめ

このアルゴリズムは「増加路（augmenting path）」の考え方に基づいた手法で、計算量はO(V×E)です。応募者と求人の割り当てのような二部グラフ上のマッチング問題を効率的に解くことができ、競技プログラミングや実務のシステム設計の両方で広く活用されています。