네트워크 플로우 알고리즘(Network Flow Algorithm)은 그래프 이론에서 사용되며, 최대 유량(maximum flow)을 찾는 알고리즘이다. 유량(flow)은 한 노드에서 다른 노드로의 데이터 전송량을 의미한다.
예를 들어, 기름을 전송하는 파이프(pipe)를 떠올려보자. 각 파이프는 지름 등의 요인으로 인해 한 번에 전송할 수 있는 용량(Capacity)를 가진다. 여러 파이프가 연결된 경우를 생각해보자. 연결된 긴 파이프의 용량은 몇인가? 연결된 파이프들의 용량 중 가장 작은 값과 같다.
네트워크 유량의 특징들이 존재한다. 잘 정리되어 있는 블로그에서 확인할 수 있다. 알고리즘 증명은 갓사과님 블로그에서 확인할 수 있다.
두 노드간의 최대 유량을 구하는 알고리즘 중 하나가 에드몬드 카프(Edmonds-Karp) 알고리즘이다. 이 알고리즘은 너비 우선 탐색(Breadth-First Search, BFS) 알고리즘을 사용하여 최대 용량을 찾는다. 시간 복잡도는 O(VE^2)이다.
에드몬드-카프 알고리즘의 동작 방식은 다음과 같다.
- 초기에는 최대 용량을 0으로 설정합니다.
- BFS 알고리즘을 사용하여 시작 노드에서 도착 노드까지의 경로를 찾습니다.
- 경로에서 최소 용량을 찾습니다.
- 경로 상의 각 간선에 대해 최소 용량을 빼고, 그 값으로 최대 용량을 더합니다.
- 2번부터 4번까지 반복합니다.
먼저 전체 코드를 보자.
int n, capacity[100][100], flow[100][100], parent[100];
vector<int> edge[100];
int maxFlow(int start, int end) {
int result = 0;
while (1) {
fill(parent, parent + 100, -1);
queue<int> q;
q.push(start);
while (!q.empty()) {
int here = q.front();
q.pop();
for (int i = 0; i < edge[here].size(); ++i) {
int there = edge[here][i];
if (parent[there] == -1 && capacity[here][there] > flow[here][there]) {
q.push(there);
parent[there] = here;
if (there == end) break;
}
}
}
if (parent[end] == -1) break;
int minCapacity = MAXINT;
int here = end;
while (here != start) {
minCapacity = min(minCapacity, capacity[parent[here]][here] - flow[parent[here]][here]);
here = parent[here];
}
here = end;
while (here != start) {
flow[parent[here]][here] += minCapacity;
flow[here][parent[here]] -= minCapacity;
here = parent[here];
}
result += minCapacity;
}
return result;
}먼저 전역 변수의 의미를 파악하자.
- n: 노드 개수
- capacity[][]: 각 네트워크(파이프)의 용량
- flow[][]: 해당 네트워크에 흘러보내고 있는 유량
- parent[]: 흘러보낼 경로를 역추적하며 파악하기 위해 선언. -1이면 아직 탐색하지 않는 노드.
- vector edge[]: 그래프 엣지
while (1) {
fill(parent, parent + 100, -1);
queue<int> q;
q.push(start);
...
}에드몬드 카프 알고리즘은 BFS를 여러번 수행한다. 먼저 parent[]를 -1로 초기화 후 시작노드를 queue에 넣어 탐색할 준비를 한다.
while (!q.empty()) {
int here = q.front();
q.pop();
for (int i = 0; i < edge[here].size(); ++i) {
int there = edge[here][i];
// 방문하지 않고, 유량을 추가로 흘러보낼 수 있는 노드 탐색
if (parent[there] == -1 && capacity[here][there] > flow[here][there]) {
q.push(there);
parent[there] = here;
if (there == end) break;
}
}
}가장 일반적인 BFS 구현이다. 이때 if문에 보면 capacity보다 flow가 작아야 탐색을 하게 되는 부분만 주의하면 된다.
if (parent[end] == -1) break;end 노드를 방문하지 않았다는 것은 더 이상 유량을 흘러보낼 방법이 없다는 것이다. 따라서 최대 유량을 구했을 것을 보장하므로 break를 통해 while(1)을 빠져나와 함수를 종료하게 된다.
int minCapacity = MAXINT;
int here = end;
while (here != start) {
minCapacity = min(minCapacity, capacity[parent[here]][here] - flow[parent[here]][here]);
here = parent[here];
}연결된 경로의 네트워크(파이프) 중 현재 추가로 흘러보낼 수 있는 최소 유량을 구한다. 이때 parent[]를 이용해 end 노드부터 역추적하며 경로를 따라간다.
here = end;
while (here != start) {
flow[parent[here]][here] += minCapacity;
flow[here][parent[here]] -= minCapacity;
here = parent[here];
}
result += minCapacity;minCapacity을 구했다면 다시 역추적하며 네트워크에 흘러보낼 유량을 더한다. result는 우리가 구하고자 하는 최대 유량을 뜻하는 변수이다.
네트워크 플로우는 최대 유량 문제 외에도, 최소 컷(minimum cut), 이분 탐색, MCMF 등 여러 문제로 나눠진다. 또한 이 게시물에서 본 최대 유량 문제(maximum flow)도 여러 알고리즘이 존재하고, 현재도 연구 중이라고 한다. 다른 알고리즘에 대해서는 추후에 시리즈로 작성할 예정이다.
Reference
