[알고리즘] 네트워크 플로우 (Network Flow) - 에드몬드 카프 알고리즘 (Edmonds-Karp)

네트워크 플로우 (Network Flow) - 에드몬드 카프 알고리즘 (Edmonds-Karp)

네트워크 플로우(Network Flow)는 한 정점에서 다른 정점까지 흐를 수 있는 데이터의 최대 크기가 어느 정도인지를 확인하는 알고리즘입니다. 유향 그래프에서 각 간선은 데이터가 흐를 수 있는 정해진 용량으로 제한되어 있으며 이를 최대한의 양으로 얼마나 흐르게 할 수 있는 지를 확인합니다. 이것을 최대 유량 문제(Max Flow)로 정의하며 해결하기 위한 알고리즘으로 에드몬드 카프 알고리즘(Edmonds-Karp)을 적용합니다.

 

또한 네트워크 플로우는 도로망의 교통 흐름을 분석하거나 전자 회로의 전류, 배수관을 흐르는 유체, 유량 등을 연구하는데 적용됩니다.

 

현재 흐르고 있는 데이터의 양을 유량, 간선에 흐를 수 있는 최대 데이터의 양을 용량이라 표현하겠습니다.

위 그래프에서 A에서 D까지 최대한으로 유량을 보내고자 합니다. 그러면 A에서 유량 7을 내보내면 되는 것일까요?

당연히 안됩니다. B까지 가는데는 성공하지만 C까지 갈 수 있는 최대 용량을 벗어났습니다. 

따라서 A에서 D까지 막힘없이 흐를 수 있는 최적의 유량은 5가 됩니다. 경로 상에서 가장 적은 용량이 5이기 때문입니다. 이러한 문제를 해결하는 알고리즘이 에드몬드 카프 알고리즘입니다.

 

알고리즘 원리

위 예시를 통해 원리를 좀 더 자세히 알아보겠습니다. 정점 1에서 정점 6까지 지날 수 있는 최대 유량 문제를 해결하기 위해서 너비 우선 탐색(BFS)을 활용하여 가능한 모든 경우의 수를 탐색합니다. 우선 위와 같이 현재 유량을 0으로 초기화하고 제한된 간선의 용량안에서 유량을 반복적으로 더하는 과정을 진행합니다.

1-2-3-6 의 경로를 보겠습니다. 흐를 수 있는 최대 유량은 5이므로 5씩 더해줍니다. 2-3의 용량은 포화되었습니다.

1-2-6 의 경로를 보겠습니다. 2-6으로 보낼 수 있는 유량이 10이지만 1-2의 남은 용량이 9이므로 9씩 더해줍니다. 이것으로 인해 1-2의 용량은 포화되었습니다.

1-4-5-3-6 의 경로를 보겠습니다. 3-6의 남은 용량이 3이므로 3씩 더해줍니다. 이것으로 인해 3-6의 용량도 포화되었습니다.

1-4-5-6 의 경로를 보겠습니다. 5-6의 용량이 7이므로 7씩 더해줍니다. 이것으로 인해 5-6의 용량도 포화되었습니다.

 

이제 유량을 보낼 수 있는 경우의 수가 모두 제거된 것처럼 보이지만 최대 유량을 계산하는 알고리즘의 중요한 내용 중 음의 유량을 계산할 수 있다는 사실이 존재합니다. 가능한 모든 경로를 탐색하기 위해 음의 유량도 고려합니다. 

음의 유량은 실제로는 존재하지 않는 개념이지만 유량을 더하는 과정에서 유량이 지나가는 방향의 반대 방향으로는 유량이 빠지고 있다고 보면 됩니다.

2-3 의 경로를 보겠습니다. 정점 2에서 정점 3으로 유량이 5라는 사실은 정점 3에서 정점 2로 -5만큼의 유량이 흐른다는 사실로 이해하면 됩니다. 즉, 용량은 5이며 유량이 -5인 것으로 판단합니다. 이렇게하면 남아있는 경로를 좀 더 찾아낼 수 있습니다. 

바로 위와 같이 1-4-5-3-2-6 의 또다른 경로를 찾아낼 수 있습니다. 1만큼의 유량을 추가로 보낼 수 있고 2-3 경로에서는 1의 유량을 역으로 빼야합니다. 이러한 방식으로 음의 경로를 고려해 최적의 유량을 계산할 수 있습니다.

 

이제 더이상의 경로가 존재하지 않으므로 위 그래프에서의 최대 유량은 14 + 11 = 25가 됩니다. 시작 정점이 정점 1이므로 정점 1의 진출 간선에 해당하는 유량을 모두 더해주시면 됩니다. 또한 특별한 조건이 없는 이상 최대 유량 알고리즘의 동작 순서는 고려하지 않아도 됩니다.

 

알고리즘 원리

// Algorithm Analysis
// 네트워크 플로우 (Network Flow)

#include <iostream>
#include <vector>
#include <queue>

#define MAX 100
#define INF 1000000000

using namespace std;

int n = 6;
int result;
int cap[MAX][MAX]; // 용량
int flow[MAX][MAX]; // 현재 유량
int vtd[MAX]; // 현재 정점 방문 여부

vector<int> a[MAX];

// 최대 유량 계산
void maxFlow(int s, int e) {
	while (1) {
		fill(vtd, vtd + MAX, -1);
		queue<int> q;
		q.push(s);
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (int i = 0; i < a[x].size(); i++) {
				int j = a[x][i]; // 인접 정점 가져옴
				// 방문하지 않은 정점 중 용량이 남은 경우
				if (cap[x][j] - flow[x][j] > 0 && vtd[j] == -1) { // 흐를 수 있는 경우 && 방문하지 않은 경우
					q.push(j);
					vtd[j] = x; // 경로를 기억함
					if (j == e) break; // 도착지에 도달한 경우
				}
			}
		}
		// 모든 경로를 다 찾은 경우
		if (vtd[e] == -1) break;
		int f = INF;
		// 거꾸로 최소 유량 탐색
		for (int i = e; i != s; i = vtd[i]) {
			f = min(f, cap[vtd[i]][i] - flow[vtd[i]][i]);
		}
		// 최소 유량만큼 추가
		for (int i = e; i != s; i = vtd[i]) {
			flow[vtd[i]][i] += f;
			flow[i][vtd[i]] -= f;
		}
		result += f;
	}
}

int main() {
	a[1].push_back(2);
	a[2].push_back(1);
	cap[1][2] = 14;

	a[1].push_back(4);
	a[4].push_back(1);
	cap[1][4] = 12;

	a[2].push_back(3);
	a[3].push_back(2);
	cap[2][3] = 5;

	a[2].push_back(4);
	a[4].push_back(2);
	cap[2][4] = 4;

	a[2].push_back(5);
	a[5].push_back(2);
	cap[2][5] = 6;

	a[2].push_back(6);
	a[6].push_back(2);
	cap[2][6] = 10;

	a[3].push_back(6);
	a[6].push_back(3);
	cap[3][6] = 8;

	a[4].push_back(5);
	a[5].push_back(4);
	cap[4][5] = 11;

	a[5].push_back(3);
	a[3].push_back(5);
	cap[5][3] = 4;

	a[5].push_back(6);
	a[6].push_back(5);
	cap[5][6] = 7;

	maxFlow(1, 6);
	printf("최대 유량 : %d", result);
}
// 최대 유량 : 25

 

시간복잡도 : O(VE^2)

에드몬드 카프 알고리즘의 시간복잡도는 O(VE^2)로써 (정점 수 * 간선 수)의 제곱입니다. 

네트워크 플로우는 에드몬드 카프 알고리즘 외에 더 빠른 알고리즘도 존재하며 이분 매칭 등의 알고리즘으로 다양하게 확장이 가능한 알고리즘입니다.

 

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.