에드몬드-카프(Edmonds-Karp)

에드몬드-카프(Edmonds-Karp) 알고리즘이란?

에드몬드-카프 알고리즘은 포드-풀커슨(Ford-Fulkerson) 방법을 기반으로 네트워크에서 최대 유량을 찾는 알고리즘입니다.

DFS를 이용해 증가 경로(Augmenting Path)를 찾는 구체적인 방법을 명시하지 않는 것과 달리, 에드몬드-카프 알고리즘은 너비 우선 탐색(BFS) 을 사용하여 가장 짧은 증가 경로를 찾는다는 점이 핵심적인 차이입니다.

---

특징

• 증가 경로 탐색: 소스(S)에서 싱크(T)까지의 증가 경로를 너비 우선 탐색(BFS)으로 찾습니다.
• 최단 경로 보장: BFS를 사용하므로, 간선의 수가 가장 적은 증가 경로를 항상 먼저 찾게 됩니다.
• 시간 복잡도: 이 방식은 포드-풀커슨 방법의 시간 복잡도를 개선하여, 특정 상황에서 더 효율적으로 동작합니다.

---

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
const int INF = 1e9;
const int MAX_V = 50; // 최대 정점 개수
 
int V; // 정점의 수
int capacity[MAX_V][MAX_V]; // capacity[u][v]: u -> v 간선의 용량
vector<int> adj[MAX_V];     // 인접 리스트
 
// 에드몬드-카프 알고리즘
int max_flow(int source, int sink) {
    int total_flow = 0;
 
    // 증가 경로가 없을 때까지 반복
    while (true) {
        // BFS를 사용하여 증가 경로를 찾음
        vector<int> parent(V, -1);
        queue<int> q;
 
        parent[source] = source;
        q.push(source);
 
        while (!q.empty() && parent[sink] == -1) {
            int u = q.front();
            q.pop();
 
            for (int v : adj[u]) {
                // 방문하지 않았고, 잔여 용량이 남아있는 경우
                if (parent[v] == -1 && capacity[u][v] > 0) {
                    parent[v] = u;
                    q.push(v);
                }
            }
        }
 
        // 싱크에 도달하는 증가 경로가 없으면 종료
        if (parent[sink] == -1) {
            break;
        }
 
        // 경로의 최소 잔여 용량(보낼 수 있는 유량)을 찾음
        int path_flow = INF;
        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            path_flow = min(path_flow, capacity[u][v]);
        }
 
        // 경로에 유량을 흘려보냄 (잔여 용량 업데이트)
        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            capacity[u][v] -= path_flow; // 정방향 간선 용량 감소
            capacity[v][u] += path_flow; // 역방향(유령) 간선 용량 증가
        }
 
        // 총 유량에 더함
        total_flow += path_flow;
    }
 
    return total_flow;
}
 
int main() {
    // 예제 그래프 설정
    // 6개의 정점 (0 ~ 5)
    // 소스: 0, 싱크: 5
    V = 6;
    int source = 0, sink = 5;
 
    // 간선과 용량 추가 (u, v, cap)
    vector<tuple<int, int, int>> edges = {
        {0, 1, 16}, {0, 2, 13}, {1, 2, 10}, {1, 3, 12}, {2, 1, 4},
        {2, 4, 14}, {3, 2, 9},  {3, 5, 20}, {4, 3, 7},  {4, 5, 4}
    };
    
    for (const auto& edge : edges) {
        int u, v, cap;
        tie(u, v, cap) = edge;
        adj[u].push_back(v);
        adj[v].push_back(u); // 역방향 경로 탐색을 위해 추가
        capacity[u][v] = cap;
    }
 
    cout << "최대 유량: " << max_flow(source, sink) << endl; // 결과: 23
 
    return 0;
}

자세한 유량 계산 과정은 최대 유량(Maximum Flow) 문제 의 포드-풀커슨 방법과 동일합니다.