C++로 구현하는 Edmonds-Karp 알고리즘: 최대 유량(Max Flow) 계산 프로그램

이 글에서는 그래프 이론의 대표적인 문제인 최대 유량(Maximum Flow)을 계산하기 위한 Edmonds-Karp 알고리즘을 C++로 구현하는 방법을 소개합니다. Edmonds-Karp 알고리즘은 Ford-Fulkerson 방법에 너비 우선 탐색(BFS)을 적용한 알고리즘으로, 시작 정점(소스)과 도착 정점(싱크) 사이의 최대 유량을 다항 시간 내에 효율적으로 구할 수 있습니다.

알고리즘 개요

Edmonds-Karp 알고리즘의 핵심 동작 과정은 다음과 같습니다.

시작
    edmondsKarp() 함수:
        유량(flow)을 0으로 초기화한다.
        소스에서 싱크까지 증가 경로(augmenting path)가 존재하면,
        해당 경로의 유량을 현재 유량에 더한다.
        더 이상 증가 경로가 없으면 최종 유량을 반환한다.
끝

여기서 증가 경로란 잔여 용량(residual capacity)이 남아 있는 간선들로만 구성된 소스-싱크 경로를 의미합니다. BFS를 통해 증가 경로를 찾고, 찾은 경로를 따라 유량을 누적하는 과정을 반복하면서 최대 유량을 계산합니다.

C++ 예제 코드

#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
int c[10][10];              // 간선 용량 저장
int flowPassed[10][10];     // 이미 흐른 유량 저장
vector<int> g[10];          // 인접 리스트(그래프)
int parList[10];            // BFS 경로 추적용 부모 노드 배열
int currentPathC[10];       // 현재 경로의 최소 잔여 용량

int bfs(int sNode, int eNode) // 너비 우선 탐색(BFS)
{
    memset(parList, -1, sizeof(parList));
    memset(currentPathC, 0, sizeof(currentPathC));
    queue<int> q; // 큐 선언
    q.push(sNode);
    parList[sNode] = -1;      // 소스 노드 초기화
    currentPathC[sNode] = 999; // 소스 노드의 용량을 충분히 큰 값으로 설정
    while(!q.empty()) // 큐가 비어 있지 않은 동안 반복
    {
        int currNode = q.front();
        q.pop();
        for(int i=0; i<g[currNode].size(); i++)
        {
            int to = g[currNode][i];
            if(parList[to] == -1)
            {
                if(c[currNode][to] - flowPassed[currNode][to] > 0)
                {
                    parList[to] = currNode;
                    currentPathC[to] = min(currentPathC[currNode],
                    c[currNode][to] - flowPassed[currNode][to]);
                    if(to == eNode)
                    {
                        return currentPathC[eNode];
                    }
                    q.push(to);
                }
            }
        }
    }
    return 0;
}

int edmondsKarp(int sNode, int eNode)
{
    int maxFlow = 0;
    while(true)
    {
        int flow = bfs(sNode, eNode);
        if (flow == 0)
        {
            break; // 더 이상 증가 경로가 없으면 종료
        }
        maxFlow += flow;
        int currNode = eNode;
        while(currNode != sNode)
        {
            int prevNode = parList[currNode];
            flowPassed[prevNode][currNode] += flow; // 순방향 유량 추가
            flowPassed[currNode][prevNode] -= flow; // 역방향 유량 감소
            currNode = prevNode;
        }
    }
    return maxFlow;
}

int main()
{
    int nodCount, edCount;
    cout<<"노드 수와 간선 수를 입력하세요\n";
    cin>>nodCount>>edCount;
    int source, sink;
    cout<<"소스와 싱크를 입력하세요\n";
    cin>>source>>sink;
    for(int ed = 0; ed < edCount; ed++)
    {
        cout<<"시작 정점, 끝 정점, 용량을 입력하세요\n";
        int from, to, cap;
        cin>>from>>to>>cap;
        c[from][to] = cap;
        g[from].push_back(to);
        g[to].push_back(from);
    }
    int maxFlow = edmondsKarp(source, sink);
    cout<<endl<<endl<<"최대 유량:"<<maxFlow<<endl;
}

코드 설명

bfs() 함수

BFS는 큐를 사용하여 소스 노드부터 시작해 인접 노드를 차례로 탐색합니다. 각 노드를 방문할 때 c[currNode][to] - flowPassed[currNode][to], 즉 잔여 용량이 0보다 큰 경우에만 경로를 확장합니다. 도중 싱크 노드에 도달하면 해당 경로에서 흐를 수 있는 최소 용량(currentPathC)을 즉시 반환합니다.

edmondsKarp() 함수

BFS가 반환한 유량이 0이면 더 이상 증가 경로가 없다는 뜻이므로 반복을 종료합니다. 유량이 존재하면 최대 유량에 더하고, 부모 노드 배열(parList)을 따라 경로를 거슬러 올라가며 순방향 간선에는 유량을 더하고 역방향 간선에는 유량을 빼줍니다. 이렇게 하면 나중에 역방향 간선을 통해 유량을 되돌릴 수 있는 잔여 그래프(residual graph)가 자연스럽게 구성됩니다.

실행 결과 예시

노드 수와 간선 수를 입력하세요
6
7
소스와 싱크를 입력하세요
0
4
시작 정점, 끝 정점, 용량을 입력하세요
0
1
14
시작 정점, 끝 정점, 용량을 입력하세요
2
4
10
시작 정점, 끝 정점, 용량을 입력하세요
6
7
9
시작 정점, 끝 정점, 용량을 입력하세요
5
2
10
시작 정점, 끝 정점, 용량을 입력하세요
1
4
12
시작 정점, 끝 정점, 용량을 입력하세요
2
0
15
시작 정점, 끝 정점, 용량을 입력하세요
5
3
15
최대 유량:12

위 실행 결과에서 소스(0)에서 싱크(4)까지 흐를 수 있는 최대 유량은 12로 계산됩니다. 이는 네트워크 플로우 문제에서 병목 구간의 용량 제약에 따라 결정되는 값입니다.

마무리

Edmonds-Karp 알고리즘은 시간 복잡도가 O(V·E²)(V는 정점 수, E는 간선 수)로 알려져 있으며, Ford-Fulkerson 방법처럼 무한 루프에 빠지지 않는다는 장점이 있습니다. 네트워크 트래픽 분석, 물류 배송 경로 최적화, 파이프라인 용량 설계 등 다양한 실무 문제에 활용될 수 있으니, 위 코드를 직접 컴파일하고 다양한 그래프 입력으로 실험해 보시기 바랍니다.