유량 알고리즘에 대한 메모 2: 디닉, 호프크로프트-카프

추가로 참고한 글

https://cookiehcl.tistory.com/4

Hopcroft–Karp bipartite matching algorithm

 

https://blog.naver.com/kks227/220816033373

호프크로프트 카프 알고리즘 (Hopcroft-Karp Algorithm) (수정: 2020-09-30)

 

이전 글에서 쓴 정리: 최단 경로로 유량을 보내면 최단 경로의 길이는 단조증가한다

 

디닉 알고리즘: 최단 경로가 같은 유량을 묶어서 보낸다, 시간복잡도 $O(V^2E)$

구체적으로 다음 단계를 반복함

1. 잔여 그래프에서 BFS DAG 만들기

2. DAG 위에서 유량을 더 보낼 수 없을 때까지 DFS로 아무 경로나 찾아 보내기, 이때 병목 간선은 지우고 간선 삭제 때문에 더 이상 싱크 정점으로 도달할 수 없는 정점도 지움

 

최단 경로의 길이가 t일 때 1, 2단계를 한 번 수행하면 길이가 t인 경로가 모두 없어진다. 유량을 흘려 역방향 간선이 생기더라도 최단 경로가 t인 경로는 반드시 처음에 만든 BFS DAG에 포함되기 때문이다. (정확한 증명은 https://gazelle-and-cs.tistory.com/84 참고) 가능한 최단 경로의 길이는 V가지이니 1, 2단계는 최대 V번 반복된다. 1단계의 시간복잡도는 자명히 O(E)이니 2단계가 O(VE)임을 보이면 전체 $O(V^2E)$임을 증명할 수 있다.

2단계에서 삭제된 정점과 간선을 재방문하는 경우를 생각하지 않으면 DAG 위에서 구하기 때문에 경로 하나를 O(V)에 찾을 수 있고, 경로 하나를 찾을 때마다 간선이 하나씩 지워지니 최단 경로를 찾는 횟수는 최대 E번이다. 따라서 재방문을 무시하면 2단계의 시간복잡도는 O(VE)이다. 정점/간선 삭제는 O(1)에 수행할 수 있고, 삭제된 정점/간선은 재방문하지 않게 처리하면 막다른 길로 인해 되돌아가는 시간은 2단계 전체에서 O(E)이다. 따라서 2단계의 전체 시간복잡도는 O(VE)이고, 디닉 알고리즘의 전체 시간복잡도는 $O(V^2E)$이다.

 

다음은 디닉 알고리즘의 구현이다. 작년 알로하 강의(by andrewmjk1)에서 제공해 주신 코드를 많이 참고했다(사실상 같은 코드이다). 

 

template <typename T = int>
struct Dinic {
    struct Edge{
        int to, rev;
        T f, c;
        Edge(int to, int rev, T f, T c) : to(to), rev(rev), f(f), c(c) {}
    };
    vector<vector<Edge>> G;
    vector<int> ptr, lev;
    
    int N, src, sink;
    T inf;
    Dinic(int N) : N(N), ptr(N+1), lev(N+1), G(N+1), src(-1), sink(-1), inf(0) {}
    Dinic(int N, int src, int sink) : Dinic(N) { this->src = src, this->sink = sink; }
    void addEdge(int a, int b, T cap) {
        inf = max(inf, cap);
        G[a].emplace_back(b, G[b].size(), 0, cap);
        G[b].emplace_back(a, G[a].size()-1, 0, 0);
    }
    int bfs() {
        fill(lev.begin(), lev.end(), -1);
        lev[src] = 0;
        queue<int> q;
        q.push(src);
        while (q.size()) {
            int v = q.front();
            q.pop();
            for (Edge& i : G[v]) {
                if (lev[i.to] == -1 and i.f < i.c) {
                    lev[i.to] = lev[v] + 1;
                    q.push(i.to);
                }
            }
        }
        return lev[sink] != -1;
    }
    T dfs(int v, T flow) {
        // init ptr vector before calling dfs
        if (v == sink) return flow;
        for (int& i = ptr[v]; i < G[v].size(); i++) {
            auto& E = G[v][i];
            if (lev[E.to] != lev[v]+1 or E.f == E.c) continue;
            T ret = dfs(E.to, min(flow, E.c - E.f));
            if (ret) {
                E.f += ret;
                G[E.to][E.rev].f -= ret;
                return ret; 
            }
        }
        return 0;
    }
    T maxflow(){
        T ret = 0;
        while (bfs()) {
            // edit this part if nodes are 0-indexed
            fill(ptr.begin(), ptr.end(), 0);
            while (1){
                T flow = dfs(src, inf);
                if (!flow) break;
                ret += flow;
            }
        }
        return ret;
    }
    tuple<T, vector<int>, vector<int>> mincut() {
        T ret = maxflow();
        vector<int> l, r;
        // edit this part if nodes are 0-indexed
        for (int i = 1; i <= N; i++){
            if (lev[i] == -1) r.push_back(i);
            else l.push_back(i);
        }
        return {ret, l, r};
    }
};

 

최대 이분 매칭 문제는 최대 유량 문제로 환원할 수 있고, 환원한 형태에서 최대 유량의 크기 f <= V이므로 포드 풀커슨 방법을 쓰면 O(VE)에 풀 수 있다.

디닉 알고리즘을 매칭 알고리즘에 적용한 것이 호프크로프트-카프 알고리즘이다. 이분 매칭 문제를 유량 문제로 환원했을 때 모든 간선의 용량은 1이며, 이러한 그래프에 디닉 알고리즘을 적용하면 수행 시간의 상한이 $O(E \sqrt{V})$가 된다. 이는 다음 lemma로 보일 수 있다.

 

lemma: 디닉 알고리즘을 수행하며 찾는 최단 경로의 서로 다른 길이의 수는 $2\sqrt{V}$개 이하이다.

pf) 길이가 $\sqrt{V}$ 이하인 경우와 초과인 경우를 나누어 생각하자. $\sqrt{V}$ 이하인 길이는 자명히 $\sqrt{V}$개 이하이다. 최대 유량이 V 이하이므로 증가 경로의 개수 또한 최대 V개이며, 그중 길이가 $\sqrt{V}$ 이상인 최단 경로의 수는 $\sqrt{V}$개 이하이다. 따라서 길이의 수는 $2\sqrt{V}$개 이하이다.

 

모든 간선의 용량이 1이기 때문에 어떤 경로로 유량을 보내면 경로에 속한 모든 간선이 병목이 되어 지워진다. 따라서 길이가 같은 경로를 모두 찾는 시간복잡도는 O(E)이며, 이를 최대 $2\sqrt{V}$번 반복하니 전체 시간복잡도는 $O(E\sqrt{V})$이다. 

 

모든 간선의 용량이 1인 그래프에서 디닉을 쓸 때 시간복잡도를 더 타이트하게 $O(min(V^{2/3}, E^{1/2})E)$라고도 하는데 이건 아직 모르겠다

 

이분 매칭을 구현할 때 보통 간소화된 형태를 쓰는 것처럼, 호프크로프트-카프도 간소화된 형태의 구현을 주로 사용한다. 구현은 https://github.com/justiceHui/icpc-teamnote/blob/master/pdf/240919-icpc-world-finals-astana.pdf 등 뛰어난 팀의 팀노트를 참고하자. 기본 이분 매칭의 구현에서 BFS DAG를 추가한 형태라고 생각해도 무방해 보인다.

 

아래는 대jhnah917 팀노트와 kks227님 블로그를 참고한 구현체이다. dfs를 통해 길이가 같은 최단 경로를 찾을 때 한 번 유량을 흘린 정점/간선은 지워야 하지만, BFS DAG와 이분 그래프, 구현 방법의 특성상 명시적으로 처리하지 않아도 된다고 한다. 이건 완전히 이해하진 못했는데 그런갑다 하고 쓰고 있다.

struct HK {
    vector<int> l, r, lev;
    vector<vector<int>> G;
    int L, R;
    HK(int L, int R) : L(L), R(R), G(L+1), l(L+1), r(R+1), lev(L+1) {}
    void addEdge(int a, int b) {
        G[a].push_back(b);
    }
    int bfs(){
        queue<int> q;
        for (int i = 1; i <= L; i++){
            if (!l[i]){
                lev[i] = 0;
                q.push(i);
            }
            else lev[i] = -1;
        }
        int ret = 0;
        while (q.size()){
            int v = q.front();
            q.pop();
            for (int i : G[v]){
                if (!r[i]) ret = 1;
                else if (lev[r[i]] == -1){
                    lev[r[i]] = lev[v]+1;
                    q.push(r[i]);
                }
            }
        }
        return ret;
    }
    int dfs(int v){
        for (int i : G[v]){
            if (!r[i] or (lev[r[i]] == lev[v]+1 and dfs(r[i]))){
                r[i] = v;
                l[v] = i;
                return 1;
            }
        }
        return 0;
    }
    int maxMatch(){
        int ret = 0;
        while (bfs()){
            for (int i = 1; i <= L; i++){
                if (!l[i] and dfs(i))
                    ret++;
            }
        }
        return ret;
    }
};