Ford-Fulkerson 알고리즘은 흐름 네트워크의 최대 흐름 문제를 해결하기 위해 널리 사용되는 알고리즘입니다. 최대 흐름 문제는 가장자리의 용량 제약에 따라 방향성 가중치 그래프에서 소스 정점에서 싱크 정점으로 전송될 수 있는 흐름의 최대량을 결정하는 것과 관련됩니다.
알고리즘은 잔여 그래프, 즉 각 에지의 용량에서 전류 흐름을 뺀 그래프에서 소스에서 싱크까지의 경로인 증가 경로를 반복적으로 찾는 방식으로 작동합니다. 그러면 알고리즘은 경로를 따라 있는 가장자리의 최소 용량인 가능한 최대량만큼 이 경로를 따라 흐름을 증가시킵니다.
문제:
모든 에지에 용량이 있는 흐름 네트워크를 나타내는 그래프가 있습니다. 또한 두 개의 정점이 주어지면 원천 '모래 싱크대 그래프의 't'에서 다음 제약 조건을 사용하여 s에서 t로 가능한 최대 흐름을 찾습니다.
- 가장자리의 흐름은 가장자리의 주어진 용량을 초과하지 않습니다.
- 들어오는 흐름은 s와 t를 제외한 모든 정점에 대해 나가는 흐름과 같습니다.
예를 들어 CLRS 책에 있는 다음 그래프를 살펴보세요.
위 그래프에서 가능한 최대 유량은 23입니다.
권장 연습 최대 유량 찾기 시도해 보세요!
전제조건 : 최대 흐름 문제 소개
포드-풀커슨 알고리즘
다음은 Ford-Fulkerson 알고리즘의 간단한 아이디어입니다.
- 초기 흐름을 0으로 시작합니다.
- 소스에서 싱크까지 증가 경로가 존재하는 동안:
- 너비 우선 탐색 또는 깊이 우선 탐색과 같은 경로 찾기 알고리즘을 사용하여 증대 경로를 찾습니다.
- 증가 경로를 따라 보낼 수 있는 흐름의 양을 결정합니다. 이는 경로 가장자리를 따라 있는 최소 잔여 용량입니다.
- 결정된 양만큼 증가 경로를 따라 흐름을 증가시킵니다.
- 최대 흐름을 반환합니다.
시간 복잡도: 위 알고리즘의 시간 복잡도는 O(max_flow * E)입니다. 증가 경로가 있는 동안 루프를 실행합니다. 최악의 경우 매 반복마다 1개의 단위 흐름을 추가할 수 있습니다. 따라서 시간 복잡도는 O(max_flow * E)가 됩니다.
위의 간단한 알고리즘을 구현하는 방법은 무엇입니까?
먼저 구현을 이해하기 위해 필요한 잔차 그래프(Residual Graph)의 개념을 정의해보자.
잔차 그래프 플로우 네트워크의 추가 가능한 플로우를 나타내는 그래프입니다. 잔차 그래프에 소스에서 싱크로 가는 경로가 있으면 플로우를 추가하는 것이 가능합니다. 잔차 그래프의 모든 모서리에는 다음과 같은 값이 있습니다. 잔여 용량 이는 에지의 원래 용량에서 전류 흐름을 뺀 것과 같습니다. 잔여 용량은 기본적으로 엣지의 현재 용량입니다.
이제 구현 세부 사항에 대해 이야기하겠습니다. 잔차 그래프의 두 정점 사이에 간선이 없으면 잔차 용량은 0입니다. 초기 흐름이 없고 초기 잔여 용량이 원래 용량과 동일하므로 잔차 그래프를 원본 그래프로 초기화할 수 있습니다. 증가 경로를 찾으려면 잔차 그래프의 BFS 또는 DFS를 수행할 수 있습니다. 아래 구현에서는 BFS를 사용했습니다. BFS를 사용하면 소스에서 싱크로의 경로가 있는지 확인할 수 있습니다. BFS는 또한 parent[] 배열을 구축합니다. parent[] 배열을 사용하여 발견된 경로를 탐색하고 경로를 따라 최소 잔여 용량을 찾아 이 경로를 통해 가능한 흐름을 찾습니다. 나중에 발견된 경로 흐름을 전체 흐름에 추가합니다.
중요한 것은 잔차 그래프의 잔차 용량을 업데이트해야 한다는 것입니다. 경로를 따라 모든 가장자리에서 경로 흐름을 빼고 반대 가장자리를 따라 경로 흐름을 추가합니다. 나중에 흐름을 반대 방향으로 보내야 할 수 있으므로 반대 가장자리를 따라 경로 흐름을 추가해야 합니다(예를 들어 다음 링크 참조).
아래는 Ford-Fulkerson 알고리즘의 구현입니다. 단순함을 유지하기 위해 그래프는 2D 행렬로 표시됩니다.
C++
자바로 설정
// C++ program for implementation of Ford Fulkerson> // algorithm> #include> #include> #include> #include> using> namespace> std;> // Number of vertices in given graph> #define V 6> /* Returns true if there is a path from source 's' to sink> >'t' in residual graph. Also fills parent[] to store the> >path */> bool> bfs(>int> rGraph[V][V],>int> s,>int> t,>int> parent[])> {> >// Create a visited array and mark all vertices as not> >// visited> >bool> visited[V];> >memset>(visited, 0,>sizeof>(visited));> >// Create a queue, enqueue source vertex and mark source> >// vertex as visited> >queue<>int>>q;> >q.push(s);> >visited[s] =>true>;> >parent[s] = -1;> >// Standard BFS Loop> >while> (!q.empty()) {> >int> u = q.front();> >q.pop();> >for> (>int> v = 0; v if (visited[v] == false && rGraph[u][v]>0) { // 싱크 노드에 대한 연결을 찾으면 // BFS에는 더 이상 지점이 없습니다. // 부모를 설정하고 // true를 반환할 수 있습니다. if (v == t) { parent[ v] = 당신; 사실을 반환; } q.push(v); 부모[v] = 당신; 방문[v] = true; } } } // 소스에서 시작하여 BFS에서 싱크에 도달하지 않았으므로 // false return false; } // 주어진 그래프에서 s에서 t로의 최대 흐름을 반환합니다. int fordFulkerson(int graph[V][V], int s, int t) { int u, v; // 잔차 그래프를 생성하고 잔차 그래프를 // 원래 그래프의 주어진 용량으로 // 잔차 그래프의 잔차 용량으로 채웁니다. int rGraph[V] [V]; // rGraph[i][j] // i에서 j까지 // 에지의 잔여 용량을 나타내는 잔차 그래프(에지가 있는 경우 // rGraph[i][j]가 0이면 없는 것입니다.) for (u = 0; u for (v = 0; v rGraph[u][v] = graph[u][v]; int parent[V]; // 이 배열은 BFS로 채워지며 // 경로를 저장합니다. int max_flow = 0; // 처음에는 흐름이 없습니다. // 소스에서 싱크까지의 경로가 있는 동안 흐름을 강화합니다. while (bfs(rGraph, s, t, parent)) { // 가장자리의 최소 잔여 용량을 찾습니다. // BFS에 의해 채워진 경로를 따라 // 발견된 경로를 통해 최대 흐름을 찾을 수 있습니다. int path_flow = INT_MAX for (v = t; v != s; v = parent[v]) parent[v]; path_flow = min(path_flow, rGraph[u][v]) } // 경로를 따라 가장자리 및 역방향 가장자리의 잔여 용량을 업데이트합니다 for (v = t; v != s; v = parent[v]) { u = parent[v]; rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow } // 전체 흐름에 경로 흐름 추가 max_flow += path_flow; // 전체 흐름을 반환합니다. return max_flow; } // 위 함수를 테스트하기 위한 드라이버 프로그램 int main() { // 위 예제와 같은 그래프를 생성해 보겠습니다. int graph[V][V] = { { 0, 16, 13, 0, 0, 0 }, { 0, 0, 10, 12, 0, 0 }, { 0, 4, 0, 0, 14, 0 }, { 0, 0, 9, 0, 0, 20 }, { 0, 0, 0, 7 , 0, 4 }, { 0, 0, 0, 0, 0, 0 } }; 시합<< 'The maximum possible flow is ' << fordFulkerson(graph, 0, 5); return 0; }> |
>
>
자바
// Java program for implementation of Ford Fulkerson> // algorithm> import> java.io.*;> import> java.lang.*;> import> java.util.*;> import> java.util.LinkedList;> class> MaxFlow {> >static> final> int> V =>6>;>// Number of vertices in graph> >/* Returns true if there is a path from source 's' to> >sink 't' in residual graph. Also fills parent[] to> >store the path */> >boolean> bfs(>int> rGraph[][],>int> s,>int> t,>int> parent[])> >{> >// Create a visited array and mark all vertices as> >// not visited> >boolean> visited[] =>new> boolean>[V];> >for> (>int> i =>0>; i visited[i] = false; // Create a queue, enqueue source vertex and mark // source vertex as visited LinkedList queue = new LinkedList(); queue.add(s); visited[s] = true; parent[s] = -1; // Standard BFS Loop while (queue.size() != 0) { int u = queue.poll(); for (int v = 0; v if (visited[v] == false && rGraph[u][v]>0) { // 싱크 노드에 대한 연결을 찾으면 // 더 이상 BFS에 지점이 없습니다. // 부모를 설정하기만 하면 // true를 반환할 수 있습니다. if (v == t) { parent[ v] = 당신; 사실을 반환; } queue.add(v); 부모[v] = 당신; 방문[v] = true; } } } // 소스에서 시작하여 BFS의 싱크에 도달하지 못했으므로 // false를 반환합니다. return false; } // 주어진 그래프에서 s에서 t로의 최대 흐름을 반환합니다. // int fordFulkerson(int graph[][], int s, int t) { int u, v; // 잔차 그래프를 생성하고 잔차 그래프를 원본 그래프의 주어진 용량으로 // // 잔차 그래프의 잔차 용량으로 채웁니다. // rGraph[i][j]가 나타내는 잔차 그래프는 // i에서 에지까지의 잔차 용량입니다. j (가장자리가 // 있는 경우. rGraph[i][j]가 0이면 // 없는 것입니다.) int rGraph[][] = new int[V][V]; for (u = 0; u for (v = 0; v rGraph[u][v] = graph[u][v]; // 이 배열은 BFS에 의해 채워지고 경로를 저장하기 위해 int parent[] = new int[ V]; int max_flow = 0; // 초기에는 흐름이 없습니다. // 소스에서 싱크로의 경로가 있는 동안 흐름을 강화합니다. while (bfs(rGraph, s, t, parent)) { // 최소 잔여 용량을 찾습니다. // BFS에 의해 채워진 경로를 따라 // 발견된 경로를 통해 최대 흐름을 찾을 수 있습니다. int path_flow = Integer.MAX_VALUE for (v = t; v != s; v = parent[v ]) { u = parent[v]; path_flow = Math.min(path_flow, rGraph[u][v]) } // 경로를 따라 가장자리 및 역방향 가장자리의 잔여 용량을 업데이트합니다. for (v = t; v != s; v = parent[v]) { u = parent[v]; rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow } // 전체에 경로 흐름 추가 flow max_flow += path_flow; } // 전체 흐름 반환 return max_flow; } // 위 함수를 테스트하기 위한 드라이버 프로그램 public static void main(String[] args) throws java.lang.Exception { // 표시된 그래프를 생성해 보겠습니다. 위의 예에서 int graph[][] = new int[][] { { 0, 16, 13, 0, 0, 0 }, { 0, 0, 10, 12, 0, 0 }, { 0, 4 , 0, 0, 14, 0 }, { 0, 0, 9, 0, 0, 20 }, { 0, 0, 0, 7, 0, 4 }, { 0, 0, 0, 0, 0, 0 } }; MaxFlow m = 새로운 MaxFlow(); System.out.println('가능한 최대 흐름은 ' + m.fordFulkerson(graph, 0, 5)); } }> |
>
Java에서 배열 반환
>
파이썬
# Python program for implementation> # of Ford Fulkerson algorithm> from> collections>import> defaultdict> # This class represents a directed graph> # using adjacency matrix representation> class> Graph:> >def> __init__(>self>, graph):> >self>.graph>=> graph># residual graph> >self>. ROW>=> len>(graph)> ># self.COL = len(gr[0])> >'''Returns true if there is a path from source 's' to sink 't' in> >residual graph. Also fills parent[] to store the path '''> >def> BFS(>self>, s, t, parent):> ># Mark all the vertices as not visited> >visited>=> [>False>]>*>(>self>.ROW)> ># Create a queue for BFS> >queue>=> []> ># Mark the source node as visited and enqueue it> >queue.append(s)> >visited[s]>=> True> ># Standard BFS Loop> >while> queue:> ># Dequeue a vertex from queue and print it> >u>=> queue.pop(>0>)> ># Get all adjacent vertices of the dequeued vertex u> ># If a adjacent has not been visited, then mark it> ># visited and enqueue it> >for> ind, val>in> enumerate>(>self>.graph[u]):> >if> visited[ind]>=>=> False> and> val>>0>:> ># If we find a connection to the sink node,> ># then there is no point in BFS anymore> ># We just have to set its parent and can return true> >queue.append(ind)> >visited[ind]>=> True> >parent[ind]>=> u> >if> ind>=>=> t:> >return> True> ># We didn't reach sink in BFS starting> ># from source, so return false> >return> False> > > ># Returns the maximum flow from s to t in the given graph> >def> FordFulkerson(>self>, source, sink):> ># This array is filled by BFS and to store path> >parent>=> [>->1>]>*>(>self>.ROW)> >max_flow>=> 0> # There is no flow initially> ># Augment the flow while there is path from source to sink> >while> self>.BFS(source, sink, parent) :> ># Find minimum residual capacity of the edges along the> ># path filled by BFS. Or we can say find the maximum flow> ># through the path found.> >path_flow>=> float>(>'Inf'>)> >s>=> sink> >while>(s !>=> source):> >path_flow>=> min> (path_flow,>self>.graph[parent[s]][s])> >s>=> parent[s]> ># Add path flow to overall flow> >max_flow>+>=> path_flow> ># update residual capacities of the edges and reverse edges> ># along the path> >v>=> sink> >while>(v !>=> source):> >u>=> parent[v]> >self>.graph[u][v]>->=> path_flow> >self>.graph[v][u]>+>=> path_flow> >v>=> parent[v]> >return> max_flow> > # Create a graph given in the above diagram> graph>=> [[>0>,>16>,>13>,>0>,>0>,>0>],> >[>0>,>0>,>10>,>12>,>0>,>0>],> >[>0>,>4>,>0>,>0>,>14>,>0>],> >[>0>,>0>,>9>,>0>,>0>,>20>],> >[>0>,>0>,>0>,>7>,>0>,>4>],> >[>0>,>0>,>0>,>0>,>0>,>0>]]> g>=> Graph(graph)> source>=> 0>; sink>=> 5> > print> (>'The maximum possible flow is %d '> %> g.FordFulkerson(source, sink))> # This code is contributed by Neelam Yadav> |
>
>
씨#
bash if 문
// C# program for implementation> // of Ford Fulkerson algorithm> using> System;> using> System.Collections.Generic;> public> class> MaxFlow {> >static> readonly> int> V = 6;>// Number of vertices in> >// graph> >/* Returns true if there is a path> >from source 's' to sink 't' in residual> >graph. Also fills parent[] to store the> >path */> >bool> bfs(>int>[, ] rGraph,>int> s,>int> t,>int>[] parent)> >{> >// Create a visited array and mark> >// all vertices as not visited> >bool>[] visited =>new> bool>[V];> >for> (>int> i = 0; i visited[i] = false; // Create a queue, enqueue source vertex and mark // source vertex as visited List |
>
>
자바스크립트
> // Javascript program for implementation of Ford> // Fulkerson algorithm> // Number of vertices in graph> let V = 6;> // Returns true if there is a path from source> // 's' to sink 't' in residual graph. Also> // fills parent[] to store the path> function> bfs(rGraph, s, t, parent)> {> > >// Create a visited array and mark all> >// vertices as not visited> >let visited =>new> Array(V);> >for>(let i = 0; i visited[i] = false; // Create a queue, enqueue source vertex // and mark source vertex as visited let queue = []; queue.push(s); visited[s] = true; parent[s] = -1; // Standard BFS Loop while (queue.length != 0) { let u = queue.shift(); for(let v = 0; v { if (visited[v] == false && rGraph[u][v]>0) { // 싱크 노드에 대한 연결을 찾으면 // 더 이상 BFS에 지점이 없습니다. // 부모를 설정하기만 하면 // true를 반환할 수 있습니다. if (v == t) { parent[ v] = 당신; 사실을 반환; } queue.push(v); 부모[v] = 당신; 방문[v] = true; } } } // 소스에서 시작하여 // BFS의 싱크에 도달하지 않았으므로 false를 반환합니다. return false; } // 주어진 그래프에서 // s에서 t로의 최대 흐름을 반환합니다. function fordFulkerson(graph, s, t) { let u, v; // 잔차 그래프를 생성하고 // 잔차 그래프를 주어진 용량으로 // 원래 그래프의 잔차로 채웁니다 // 잔차 그래프의 용량 // rGraph[i][j] // 가장자리의 잔차 용량을 나타내는 잔차 그래프 / / i에서 j까지(가장자리가 있는 경우 // rGraph[i][j]가 0이면 // 없는 것입니다.) let rGraph = new Array(V); for(u = 0; u { rGraph[u] = new Array(V); for(v = 0; v rGraph[u][v] = graph[u][v]; } // 이 배열은 다음으로 채워집니다. BFS 및 저장 경로 let parent = new Array(V); // 처음에는 흐름이 없습니다. let max_flow = 0; // 소스에서 싱크로의 경로가 있는 동안 흐름을 강화합니다. while (bfs(rGraph, s, t) , parent)) { // BFS로 채워진 경로를 따라 // 가장자리의 최소 잔여 용량을 찾습니다. 또는 // 찾은 경로를 통해 최대 흐름을 찾습니다. for(v = t; ; v != s; v = parent[v]) { u = parent[v]; path_flow = Math.min(path_flow, rGraph[u][v]) } // 가장자리의 잔여 용량을 업데이트합니다. 경로를 따라 역방향 가장자리 for(v = t; v != s; v = parent[v]) { u = parent[v][v] -= path_flow; = path_flow; } // 전체 흐름에 경로 흐름 추가 max_flow += path_flow; } // 전체 흐름 반환 return max_flow } // 드라이버 코드 // 위의 예에 표시된 그래프를 생성해 보겠습니다. let graph = [ [ 0 , 16, 13, 0, 0, 0 ], [ 0, 0, 10, 12, 0, 0 ], [ 0, 4, 0, 0, 14, 0 ], [ 0, 0, 9, 0, 0 , 20 ], [ 0, 0, 0, 7, 0, 4 ], [ 0, 0, 0, 0, 0, 0 ] ]; document.write('가능한 최대 흐름은 ' + fordFulkerson(graph, 0, 5)); // 이 코드는 avanitrachhadiya2155가 제공한 것입니다.> |
>
>산출
The maximum possible flow is 23>
시간 복잡도 : O(|V| * E^2) , 여기서 E는 모서리 수이고 V는 정점 수입니다.
공간 복잡도 : O(V) , 대기열을 만들었습니다.
위의 Ford Fulkerson 알고리즘 구현은 다음과 같습니다. 에드먼즈-카프 알고리즘 . Edmonds-Karp의 아이디어는 BFS가 항상 최소 수의 가장자리를 가진 경로를 선택하므로 Ford Fulkerson 구현에서 BFS를 사용하는 것입니다. BFS를 사용하면 최악의 경우 시간 복잡도를 O(VE)로 줄일 수 있습니다.2). 위의 구현은 BFS가 O(V를 사용하는 경우에도 인접 행렬 표현을 사용합니다.2) 시간, 위 구현의 시간 복잡도는 O(EV삼) (나타내다 CLRS 도서 시간 복잡도 증명용)
이는 많은 실제 상황에서 발생하므로 중요한 문제입니다. 예를 들면 주어진 트래픽 제한으로 전송을 최대화하는 것, 컴퓨터 네트워크에서 패킷 흐름을 최대화하는 것 등이 있습니다.
Max-Flow를 위한 Dinc의 알고리즘.
운동:
O(VE에서 실행되도록 위 구현을 수정합니다.2) 시간.