[C++로 배우는 알고리즘과 자료구조 심화] Day 13: 이분 그래프 매칭 (Hopcroft-Karp 알고리즘)

이분 그래프 매칭 (Bipartite Graph Matching)

이분 그래프 매칭은 두 개의 분리된 정점 집합을 가지는 그래프에서 최대 매칭을 찾는 문제입니다. 이분 그래프 매칭은 네트워크 플로우, 작업 할당 문제, 매칭 문제 등 다양한 응용 분야에서 사용됩니다.

Hopcroft-Karp 알고리즘

Hopcroft-Karp 알고리즘은 이분 그래프에서 최대 매칭을 찾는 효율적인 알고리즘입니다. 이 알고리즘은 BFS와 DFS를 결합하여 구현됩니다.

Hopcroft-Karp 알고리즘의 시간 복잡도:

• (O(\sqrt{V}E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.

Hopcroft-Karp 알고리즘 구현

다음은 C++로 Hopcroft-Karp 알고리즘을 구현한 예제입니다.

 

그래프 클래스 정의

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

// 그래프 클래스 정의
class BipartiteGraph {
public:
    BipartiteGraph(int U, int V);
    void addEdge(int u, int v);
    bool bfs();
    bool dfs(int u);
    int hopcroftKarp();

private:
    int U, V; // U: 왼쪽 집합의 정점 수, V: 오른쪽 집합의 정점 수
    std::vector<std::vector<int>> adj; // 인접 리스트
    std::vector<int> pairU, pairV, dist; // 매칭 정보와 거리 정보
};

// 그래프 생성자 정의
BipartiteGraph::BipartiteGraph(int U, int V) {
    this->U = U;
    this->V = V;
    adj.resize(U + 1);
    pairU.resize(U + 1);
    pairV.resize(V + 1);
    dist.resize(U + 1);
}

// 간선 추가 함수 정의
void BipartiteGraph::addEdge(int u, int v) {
    adj[u].push_back(v);
}

 

BFS 함수 정의

// BFS 함수 정의
bool BipartiteGraph::bfs() {
    std::queue<int> q;
    for (int u = 1; u <= U; ++u) {
        if (pairU[u] == 0) {
            dist[u] = 0;
            q.push(u);
        } else {
            dist[u] = INT_MAX;
        }
    }
    dist[0] = INT_MAX;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (dist[u] < dist[0]) {
            for (int v : adj[u]) {
                if (dist[pairV[v]] == INT_MAX) {
                    dist[pairV[v]] = dist[u] + 1;
                    q.push(pairV[v]);
                }
            }
        }
    }
    return dist[0] != INT_MAX;
}

 

DFS 함수 정의

// DFS 함수 정의
bool BipartiteGraph::dfs(int u) {
    if (u != 0) {
        for (int v : adj[u]) {
            if (dist[pairV[v]] == dist[u] + 1) {
                if (dfs(pairV[v])) {
                    pairV[v] = u;
                    pairU[u] = v;
                    return true;
                }
            }
        }
        dist[u] = INT_MAX;
        return false;
    }
    return true;
}

 

Hopcroft-Karp 함수 정의

// Hopcroft-Karp 알고리즘 함수 정의
int BipartiteGraph::hopcroftKarp() {
    std::fill(pairU.begin(), pairU.end(), 0);
    std::fill(pairV.begin(), pairV.end(), 0);
    int maxMatching = 0;
    while (bfs()) {
        for (int u = 1; u <= U; ++u) {
            if (pairU[u] == 0 && dfs(u)) {
                maxMatching++;
            }
        }
    }
    return maxMatching;
}

 

사용 예제

int main() {
    int U = 4, V = 4;
    BipartiteGraph g(U, V);

    g.addEdge(1, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 1);
    g.addEdge(3, 2);
    g.addEdge(3, 3);
    g.addEdge(4, 3);
    g.addEdge(4, 4);

    std::cout << "최대 매칭 수: " << g.hopcroftKarp() << std::endl;

    return 0;
}

 

설명

1. BipartiteGraph 클래스:
   • addEdge: 간선을 추가합니다.
   • bfs: BFS를 사용하여 거리 정보를 업데이트하고 증가 경로를 찾습니다.
   • dfs: DFS를 사용하여 증가 경로를 확장합니다.
   • hopcroftKarp: BFS와 DFS를 반복하여 최대 매칭을 찾습니다.
2. 사용 예제:
   • 이분 그래프를 생성하고 간선을 추가합니다.
   • Hopcroft-Karp 알고리즘을 사용하여 최대 매칭 수를 출력합니다.

Hopcroft-Karp 알고리즘을 사용하여 이분 그래프 매칭을 찾는 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 14: 중국인의 나머지 정리 (Chinese Remainder Theorem)"에 대해 학습하겠습니다.