포드-풀커슨(Ford-Fulkerson) 알고리즘이란?
포드-풀커슨 알고리즘은 주어진 그래프에서 시작 정점(소스, Source)에서 종착 정점(싱크, Sink)까지 흐를 수 있는 최대 유량(Maximum Flow)을 구하는 고전적인 알고리즘입니다. 이 알고리즘에서 그래프의 모든 간선(edge)에는 각각 고유한 용량(capacity)이 부여됩니다.
그래프에는 다음과 같은 두 개의 특수 정점이 존재합니다.
- 소스(Source): 나가는 간선만 존재하고, 들어오는 간선은 없습니다.
- 싱크(Sink): 들어오는 간선만 존재하고, 나가는 간선은 없습니다.
알고리즘의 핵심 제약 조건
- 간선에 흐르는 유량(flow)은 해당 간선에 주어진 용량을 초과할 수 없습니다.
- 소스와 싱크를 제외한 모든 정점에서는 들어오는 유량의 합과 나가는 유량의 합이 반드시 같아야 합니다(유량 보존 법칙).
입력과 출력
입력:
인접 행렬(adjacency matrix):
0 10 0 10 0 0
0 0 4 2 8 0
0 0 0 0 0 10
0 0 0 0 9 0
0 0 6 0 0 10
0 0 0 0 0 0
출력:
최대 유량(Maximum flow): 19
알고리즘 동작 원리
포드-풀커슨 알고리즘은 증가 경로(augmenting path)를 반복적으로 찾아 유량을 누적하는 방식으로 동작합니다. 경로 탐색에는 너비 우선 탐색(BFS)을 활용하며, 탐색 대상은 원본 그래프가 아닌 잔여 용량 그래프(residual graph)입니다. 유량을 흘려보낼 때마다 해당 경로 상의 간선들의 잔여 용량이 줄어들고, 역방향 간선의 잔여 용량은 그만큼 늘어나며, 더 이상 소스에서 싱크로 가는 경로가 존재하지 않을 때까지 이 과정을 반복합니다.
bfs(vert, start, sink)
입력: 정점 목록, 시작 노드, 싱크 노드
출력: 싱크 정점에 도달했으면 true, 그렇지 않으면 false
Begin
initially mark all nodes as unvisited
state of start as visited
predecessor of start node is φ
insert start into the queue qu
while qu is not empty, do
delete element from queue and set to vertex u
for all vertices i, in the residual graph, do
if u and i are connected, and i is unvisited, then
add vertex i into the queue
predecessor of i is u
mark i as visited
done
done
return true if state of sink vertex is visited
End
fordFulkerson(vert, source, sink)
입력: 정점 목록, 소스 정점, 싱크 정점
출력: 소스에서 싱크까지의 최대 유량
Begin
create a residual graph and copy given graph into it
while bfs(vert, source, sink) is true, do
pathFlow := ∞
v := sink vertex
while v ≠ start vertex, do
u := predecessor of v
pathFlow := minimum of pathFlow and residualGraph[u, v]
v := predecessor of v
done
v := sink vertex
while v ≠ start vertex, do
u := predecessor of v
residualGraph[u,v] := residualGraph[u,v] – pathFlow
residualGraph[v,u] := residualGraph[v,u] + pathFlow
v := predecessor of v
done
maxFlow := maxFlow + pathFlow
done
return maxFlow
End
C++ 구현 예제
다음은 위 알고리즘을 C++로 구현한 전체 코드입니다. BFS로 증가 경로를 찾고, 경로상의 최소 잔여 용량(병목 용량)만큼 유량을 흘려보내는 방식으로 동작합니다.
#include<iostream>
#include<queue>
#define NODE 6
using namespace std;
typedef struct node {
int val;
int state; //방문 상태
int pred; //선행 정점(predecessor)
}node;
int minimum(int a, int b) {
return (a<b)?a:b;
}
int resGraph[NODE][NODE]; //잔여 용량 그래프
int graph[NODE][NODE] = {
{0, 10, 0, 10, 0, 0},
{0, 0, 4, 2, 8, 0},
{0, 0, 0, 0, 0, 10},
{0, 0, 0, 0, 9, 0},
{0, 0, 6, 0, 0, 10},
{0, 0, 0, 0, 0, 0}
};
int bfs(node *vert, node start, node sink) {
node u;
int i, j;
queue<node> que;
for(i = 0; i<NODE; i++) {
vert[i].state = 0; //모든 노드를 미방문 상태로 초기화
}
vert[start.val].state = 1; //시작 노드 방문 처리
vert[start.val].pred = -1; //부모 노드 없음
que.push(start); //시작 노드를 큐에 삽입
while(!que.empty()) {
//큐에서 요소를 꺼냄
u = que.front();
que.pop();
for(i = 0; i<NODE; i++) {
if(resGraph[u.val][i] > 0 && vert[i].state == 0) {
que.push(vert[i]);
vert[i].pred = u.val;
vert[i].state = 1;
}
}
}
return (vert[sink.val].state == 1);
}
int fordFulkerson(node *vert, node source, node sink) {
int maxFlow = 0;
int u, v;
for(int i = 0; i<NODE; i++) {
for(int j = 0; j<NODE; j++) {
resGraph[i][j] = graph[i][j]; //초기에는 잔여 그래프를 원본 그래프로 설정
}
}
while(bfs(vert, source, sink)) { //BFS로 증가 경로 탐색
int pathFlow = 999;//무한대 대신 사용
for(v = sink.val; v != source.val; v=vert[v].pred) {
u = vert[v].pred;
pathFlow = minimum(pathFlow, resGraph[u][v]);
}
for(v = sink.val; v != source.val; v=vert[v].pred) {
u = vert[v].pred;
resGraph[u][v] -= pathFlow; //간선의 잔여 용량 갱신
resGraph[v][u] += pathFlow; //역방향 간선의 잔여 용량 갱신
}
maxFlow += pathFlow;
}
return maxFlow; //전체 최대 유량 반환
}
int main() {
node vertices[NODE];
node source, sink;
for(int i = 0; i<NODE; i++) {
vertices[i].val = i;
}
source.val = 0;
sink.val = 5;
int maxFlow = fordFulkerson(vertices, source, sink);
cout << "Maximum flow is: " << maxFlow << endl;
}
실행 결과
Maximum flow is: 19
시간 복잡도
일반적인 포드-풀커슨 알고리즘의 시간 복잡도는 O(E × f)입니다. 여기서 E는 간선의 수, f는 최대 유량의 크기를 의미합니다. 증가 경로를 찾을 때 BFS를 사용하는 변형인 에드몬즈-카프(Edmonds-Karp) 알고리즘의 경우, 시간 복잡도가 O(V × E²)(V는 정점의 수)로 보장되므로 실제 구현에서는 BFS 기반 탐색을 사용하는 것이 안정적입니다.