에드몬드 카프 알고리즘

네트워크 플로우

네트워크 플로우는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘이다. 이런 문제를 사용하는 곳은 도로망의 교통 흐름을 분석, 전자 회로의 전류, 배수관을 흐르는 유체, 유량등을 연구하는데 사용된다.

유량 : 현재 흐르고 있는 데이터의 양

용량 : 간선에 흐를 수 있는 최대 데이터의 양

이 문제를 빠르게 해결하기 위해 사용하는 알고리즘이 에드몬드 카프 알고리즘과 디닉 알고리즘이 있다. 이 중 에드몬드 카프 알고리즘 부터 공부했다.

에드몬드 카프(Edmonds-Karp algorithm) 설명

위 그래프는 동아리 스터디 시간에 애드몬드 카프 알고리즘을 배울 때 쓴 예시 그래프이다.

A에서 D로 갈 때 0/3 이라는 소리는 현재 유량이 0 용량이 3이라는 소리이다.

에드몬드 카프 알고리즘은 BFS를 이용한다. BFS를 이용해 가능한 모든 경우의 수를 탐색하는 것이다. 예를 들어 A에서 G까지 간다고 할 때 A→D→E→G를 가면 총 1의 유량으로 흐르게 된다. 그 뒤 A→D→F→G를 갈 시 2의 유량으로 흘러 총 3의 유량을 사용하게 되는 것이다. 에드몬드 카프 알고리즘에 중요한 점은 D→E로 유량이 흐를 때 그 반대로 E→D도 흐르게 된다. D→E 1/2 일 때 E→D -1/0 이다. 그래서 E→D로도 유량이 1 흐를 수 있다. 이렇게 모든 경우의 수를 조사해 최대 유량 알고리즘을 계산하게 된다.

 

에드몬드 카프 알고리즘 구현

vector <int> adj [2020]; // 그래프 
int c[2020][2020]; //용량 
int f[2020][2020]; //현재 유량
int d[2020]; //방문 노드
int s = 2021; //시작
int t = 2002; //방문 노드

int maxFlow(){
	 int ans = 0;
	 while(true){
			memset(d,-1,sizeof d);
			queue<int> q;
			q.push(s); //처음 가야 할 곳 시작
			while(q.size()) {
		      int x = q.front();
				  q.pop();
					for(int y : ans[x]){
              if(d[y] == -1 && c[x][y] - f[x][y] >0 ){ //방문을 안했거나 유량이 남아 있을 때
                 d[y] = x; // 가는 곳 적음
								 q.push(y);
               }
					}
		  }
		if (d[t] == -1) break;
		int flow = INT_MAX;
    for(int x = t; x != s; x = d[x]) {
        flow = min(flow, c[d[x]][x]-f[d[x]][x]); //flow 더 작은거 선택
     }
		for(int x = t; x!= s; x = d[x]) {
        f[d[x]][x] += flow; //가는 방향
				f[x][d[x]] -= flow; //반대 방향
     } 
      ans += flow;
	 }
   return ans;
}

정리

에드몬드 카프 알고리즘에 대해 공부하고 구현해 보았다. 이제 이 알고리즘에 관한 문제를 풀어봐야 겠다.