포드-풀커슨 알고리즘으로 네트워크 플로우 문제 해결하기: C++ 구현 예제

이 글에서는 포드-풀커슨(Ford-Fulkerson) 알고리즘을 활용하여 네트워크 플로우(Network Flow) 문제를 해결하는 C++ 프로그램을 소개합니다. 네트워크 플로우 문제는 시작점(source)에서 도착점(sink)까지 보낼 수 있는 최대 유량을 구하는 대표적인 그래프 알고리즘 문제로, 물류 운송, 통신망 설계 등 다양한 분야에 응용됩니다.

알고리즘 개요

전체 구현은 두 가지 핵심 함수로 구성됩니다.

시작
    bfs(): 잔여 그래프(residual graph)에서 시작점 s부터 도착점 t까지의
    경로가 존재하면 true를 반환합니다.
    → 그래프에 아직 추가로 흘려보낼 수 있는 유량이 남아 있다는 의미입니다.
끝
시작
    fordFulkerson(): 주어진 그래프의 최대 유량을 반환합니다.
    A) 유량(flow)을 0으로 초기화한다.
    B) 시작점에서 도착점까지 증가 경로(augmenting path)가 존재하는 동안,
       해당 경로의 유량을 결과에 누적한다.
    C) 최종 유량을 반환한다.
끝

동작 원리

1. BFS로 증가 경로 탐색

bfs() 함수는 큐(queue)를 이용해 잔여 그래프를 너비 우선 탐색합니다. 용량이 남아 있는 간선(g[u][v] > 0)만 따라 이동하며, 방문 여부 배열과 부모 배열(par[])에 경로 정보를 기록합니다. 도착점에 도달할 수 있다면 아직 유량을 더 보낼 여지가 있는 것입니다.

2. 병목 용량 계산 및 잔여 그래프 갱신

증가 경로가 발견되면 경로상 간선 중 가장 작은 잔여 용량(path_flow), 즉 병목(bottleneck) 값을 구합니다. 이 값이 실제로 새로 흘려보낼 수 있는 유량입니다. 이후 정방향 간선의 용량은 줄이고, 역방향 간선의 용량은 같은 만큼 늘려 잔여 그래프를 갱신합니다. 역방향 간선 덕분에 이전 선택을 되돌릴 수 있어 항상 최적해에 도달할 수 있습니다.

3. 반복 종료 조건

더 이상 증가 경로가 존재하지 않으면 탐색을 종료하고 누적된 유량을 반환합니다. 이 구현의 시간 복잡도는 O(V·E²)로 알려져 있습니다.

예제 코드

#include <iostream>
#include <climits>
#include <cstring>
#include <queue>
#define n 7
using namespace std;
bool bfs(int g[n][n], int s, int t, int par[])
{
    bool visit[n];
    memset(visit, 0, sizeof(visit));
    queue <int> q;
    q.push(s);
    visit[s] = true;
    par[s] = -1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int v=0; v<n; v++)
        {
            if (visit[v]==false && g[u][v] > 0)
            {
                q.push(v);
                par[v] = u;
                visit[v] = true;
            }
        }
    }
    return (visit[t] == true);
}
int fordFulkerson(int G[n][n], int s, int t)
{
    int u, v;
    int g[n][n];
    for (u = 0; u < n; u++)
    {
        for (v = 0; v < n; v++)
        g[u][v] = G[u][v];
    }
    int par[n];
    int max_flow = 0;
    while (bfs(g, s, t,par))
    {
        int path_flow = INT_MAX;
        for (v=t; v!=s; v=par[v])
        {
            u = par[v];
            path_flow = min(path_flow, g[u][v]);
        }
        for (v = t; v != s; v = par[v])
        {
            u = par[v];
            g[u][v] -= path_flow;
            g[v][u] += path_flow;
        }
        max_flow += path_flow;
    }
    return max_flow;
}
int main()
{
    int g[n][n] = {{0, 6, 7, 1},
        {0, 0, 4, 2},
        {0, 5, 0, 0},
        {0, 0, 19, 12},
        {0, 0, 0, 17},
        {0, 0, 0, 0}};
    cout << "The maximum possible flow is " << fordFulkerson(g, 0, 3);
    return 0;
}

실행 결과

The maximum possible flow is 3

위 예제 그래프에서 시작점 0에서 도착점 3까지 흘려보낼 수 있는 최대 유량은 3입니다. 이는 직접 간선 0→3(용량 1)과 경로 0→1→3(병목 용량 2)의 합과 일치하며, 포드-풀커슨 알고리즘이 올바르게 동작함을 확인할 수 있습니다.