C++로 에지 분리 경로(Edge-Disjoint Paths)의 최대 개수 구하기

두 정점 사이에서 동일한 간선(에지)을 공유하지 않는 경로, 즉 에지 분리 경로(edge-disjoint path)의 최대 개수를 구하는 것은 그래프 이론의 고전적인 문제입니다. 이 문제는 최대 유량(Max Flow) 문제와 밀접한 관련이 있으며, 모든 간선의 용량을 1이라고 생각하면 두 정점 간의 최대 유량 값이 곧 에지 분리 경로의 최대 수가 됩니다.

알고리즘

이 프로그램은 너비 우선 탐색(BFS)으로 증강 경로(augmenting path)를 찾는 포드-풀커슨(Ford-Fulkerson) 방식, 즉 에드몬즈-카프(Edmonds-Karp) 알고리즘을 기반으로 동작합니다.

시작
    bfs() 함수: 잔여 그래프(residual graph)에서 시작점 s부터
    도착점 t까지의 경로가 존재하면 true를 반환합니다.
    (경로가 있다는 것은 그래프에 추가 유량이 가능하다는 의미)
끝

시작
    findDisPath() 함수: 주어진 그래프의 최대 유량을 반환합니다.
    A) 유량(flow)을 0으로 초기화합니다.
    B) 시작점에서 도착점으로 가는 증강 경로가 존재하는 동안,
       해당 경로의 유량을 flow에 더합니다.
    C) flow를 반환합니다.
끝

예제 코드

#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 findDisPath(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}};
    int s=0,d=3;
    cout << " There exist maximum" << " " << findDisPath(g, s, d)<< " edgedisjoint paths from " << s <<" to "<<d;
    return 0;
}

코드 설명

bfs() 함수는 잔여 그래프 위에서 시작점 s와 도착점 t가 연결되어 있는지 확인하고, 방문 배열과 부모 배열(par[])을 채워 나중에 실제 경로를 역추적할 수 있도록 합니다.

findDisPath() 함수는 원본 그래프를 복사한 뒤, BFS로 증강 경로를 반복적으로 찾습니다. 경로가 발견되면 경로상 간선들의 최소 여유 용량(path_flow)만큼 유량을 흘려보내고, 역방향 간선에는 같은 양을 더해 잔여 용량을 갱신합니다. 더 이상 증강 경로가 존재하지 않을 때까지 이 과정을 반복한 후, 누적된 max_flow 값을 반환합니다.

실행 결과

There exist maximum 3 edge-disjoint paths from 0 to 3

즉, 정점 0에서 정점 3으로 가는 서로 간선을 공유하지 않는 경로는 최대 3개까지 존재합니다.