给出一个图，它表示一个流动网络，其中每条边都有一个容量。也给出了两个顶点 来源 “s”和 下沉 “t”在图中，找出从s到t的最大可能流量，并满足以下约束条件： （a） 边缘上的流量不会超过边缘的给定容量。 b） 除了s和t之外，每个顶点的输入流都等于输出流。
null
例如，从CLSR书中考虑下面的图表。
上图中的最大可能流量为23。
先决条件： 最大流问题简介
Ford-Fulkerson Algorithm The following is simple idea of Ford-Fulkerson algorithm:1) Start with initial flow as 0.2) While there is a augmenting path from source to sink. Add this path-flow to flow.3) Return flow.
时间复杂性： 上述算法的时间复杂度为O（max_flow*E）。我们运行一个循环，同时有一个扩展路径。在最坏的情况下，我们可能会在每个迭代中添加1个单位流。因此，时间复杂度变成O（max_flow*E）。
如何实现上述简单算法？ 让我们首先定义残差图的概念，这是理解实现所需的。
残差图 流量网络图是表示额外可能流量的图表。若在残差图中有一条从源到汇的路径，那个么可以添加流。残差图的每条边都有一个称为 剩余容量 等于边缘的初始容量减去电流。剩余容量基本上是边缘的当前容量。 现在让我们谈谈实施细节。如果残差图的两个顶点之间没有边，则残差容量为0。我们可以将残差图初始化为原始图，因为没有初始流，初始残差容量等于原始容量。为了找到增广路径，我们可以对残差图进行BFS或DFS。我们在下面的实现中使用了BFS。使用BFS，我们可以发现是否存在从源到汇的路径。BFS还构建父[]数组。使用parent[]数组，我们遍历找到的路径，并通过查找路径上的最小剩余容量来查找通过该路径的可能流量。我们稍后将找到的路径流添加到整体流中。
重要的是，我们需要更新残差图中的残差容量。我们从沿路径的所有边上减去路径流，然后沿反向边添加路径流。我们需要沿反向边添加路径流，因为以后可能需要反向发送流（例如，请参见下面的链接）。 https://www.geeksforgeeks.org/max-flow-problem-introduction/
下面是Ford Fulkerson算法的实现。为了简单起见，图形被表示为2D矩阵。
C++
// C++ program for implementation of Ford Fulkerson // algorithm #include <iostream> #include <limits.h> #include <queue> #include <string.h> 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 < V; v++) { if (visited[v] == false && rGraph[u][v] > 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 if (v == t) { parent[v] = u; return true ; } q.push(v); parent[v] = u; visited[v] = 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 int fordFulkerson( int graph[V][V], int s, int t) { int u, v; // Create a residual graph and fill the residual graph // with given capacities in the original graph as // residual capacities in residual graph int rGraph[V] [V]; // Residual graph where rGraph[i][j] // indicates residual capacity of edge // from i to j (if there is an edge. If // rGraph[i][j] is 0, then there is not) for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph[u][v] = graph[u][v]; int parent[V]; // This array is filled by BFS and to // store path int max_flow = 0; // There is no flow initially // Augment the flow while there is path from source to // sink while (bfs(rGraph, s, t, 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. int path_flow = INT_MAX; for (v = t; v != s; v = parent[v]) { u = parent[v]; path_flow = min(path_flow, rGraph[u][v]); } // update residual capacities of the edges and // reverse edges along the path for (v = t; v != s; v = parent[v]) { u = parent[v]; rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow; } // Add path flow to overall flow max_flow += path_flow; } // Return the overall flow return max_flow; } // Driver program to test above functions int main() { // Let us create a graph shown in the above example 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 } }; cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5); return 0; } |
JAVA
// 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 < V; ++i) visited[i] = false ; // Create a queue, enqueue source vertex and mark // source vertex as visited LinkedList<Integer> queue = new LinkedList<Integer>(); 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 < V; v++) { if (visited[v] == false && rGraph[u][v] > 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 if (v == t) { parent[v] = u; return true ; } queue.add(v); parent[v] = u; visited[v] = 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 int fordFulkerson( int graph[][], int s, int t) { int u, v; // Create a residual graph and fill the residual // graph with given capacities in the original graph // as residual capacities in residual graph // Residual graph where rGraph[i][j] indicates // residual capacity of edge from i to j (if there // is an edge. If rGraph[i][j] is 0, then there is // not) int rGraph[][] = new int [V][V]; for (u = 0 ; u < V; u++) for (v = 0 ; v < V; v++) rGraph[u][v] = graph[u][v]; // This array is filled by BFS and to store path int parent[] = new int [V]; int max_flow = 0 ; // There is no flow initially // Augment the flow while there is path from source // to sink while (bfs(rGraph, s, t, parent)) { // Find minimum residual capacity of the edhes // along the path filled by BFS. Or we can say // find the maximum flow through the path found. 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]); } // update residual capacities of the edges and // reverse edges along the path for (v = t; v != s; v = parent[v]) { u = parent[v]; rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow; } // Add path flow to overall flow max_flow += path_flow; } // Return the overall flow return max_flow; } // Driver program to test above functions public static void main(String[] args) throws java.lang.Exception { // Let us create a graph shown in the above example 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 = new MaxFlow(); System.out.println( "The maximum possible flow is " + m.fordFulkerson(graph, 0 , 5 )); } } |
python
# 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 |
C#
// 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 < V; ++i) visited[i] = false ; // Create a queue, enqueue source vertex and mark // source vertex as visited List< int > queue = new List< int >(); queue.Add(s); visited[s] = true ; parent[s] = -1; // Standard BFS Loop while (queue.Count != 0) { int u = queue[0]; queue.RemoveAt(0); for ( int v = 0; v < V; v++) { if (visited[v] == false && rGraph[u, v] > 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 if (v == t) { parent[v] = u; return true ; } queue.Add(v); parent[v] = u; visited[v] = 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 int fordFulkerson( int [, ] graph, int s, int t) { int u, v; // Create a residual graph and fill // the residual graph with given // capacities in the original graph as // residual capacities in residual graph // Residual graph where rGraph[i,j] // indicates residual capacity of // edge from i to j (if there is an // edge. If rGraph[i,j] is 0, then // there is not) int [, ] rGraph = new int [V, V]; for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph[u, v] = graph[u, v]; // This array is filled by BFS and to store path int [] parent = new int [V]; int max_flow = 0; // There is no flow initially // Augment the flow while there is path from source // to sink while (bfs(rGraph, s, t, parent)) { // Find minimum residual capacity of the edhes // along the path filled by BFS. Or we can say // find the maximum flow through the path found. int path_flow = int .MaxValue; for (v = t; v != s; v = parent[v]) { u = parent[v]; path_flow = Math.Min(path_flow, rGraph[u, v]); } // update residual capacities of the edges and // reverse edges along the path for (v = t; v != s; v = parent[v]) { u = parent[v]; rGraph[u, v] -= path_flow; rGraph[v, u] += path_flow; } // Add path flow to overall flow max_flow += path_flow; } // Return the overall flow return max_flow; } // Driver code public static void Main() { // Let us create a graph shown in the above example 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 = new MaxFlow(); Console.WriteLine( "The maximum possible flow is " + m.fordFulkerson(graph, 0, 5)); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // 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 < V; ++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 < V; v++) { if (visited[v] == false && rGraph[u][v] > 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 if (v == t) { parent[v] = u; return true ; } queue.push(v); parent[v] = u; visited[v] = 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 function fordFulkerson(graph, s, t) { let u, v; // Create a residual graph and fill the // residual graph with given capacities // in the original graph as residual // capacities in residual graph // Residual graph where rGraph[i][j] // indicates residual capacity of edge // from i to j (if there is an edge. // If rGraph[i][j] is 0, then there is // not) let rGraph = new Array(V); for (u = 0; u < V; u++) { rGraph[u] = new Array(V); for (v = 0; v < V; v++) rGraph[u][v] = graph[u][v]; } // This array is filled by BFS and to store path let parent = new Array(V); // There is no flow initially let max_flow = 0; // Augment the flow while there // is path from source to sink while (bfs(rGraph, s, t, parent)) { // Find minimum residual capacity of the edhes // along the path filled by BFS. Or we can say // find the maximum flow through the path found. let path_flow = Number.MAX_VALUE; for (v = t; v != s; v = parent[v]) { u = parent[v]; path_flow = Math.min(path_flow, rGraph[u][v]); } // Update residual capacities of the edges and // reverse edges along the path for (v = t; v != s; v = parent[v]) { u = parent[v]; rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow; } // Add path flow to overall flow max_flow += path_flow; } // Return the overall flow return max_flow; } // Driver code // Let us create a graph shown in the above example 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( "The maximum possible flow is " + fordFulkerson(graph, 0, 5)); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
The maximum possible flow is 23
上述Ford Fulkerson算法的实现称为 Edmonds-Karp算法 Edmonds Karp的想法是在Ford Fulkerson实现中使用BFS，因为BFS总是选择边数最少的路径。当使用BFS时，最坏情况下的时间复杂度可以降低到O（VE） 2. ).上述实现使用邻接矩阵表示，尽管BFS取O（V） 2. )时间，上述实现的时间复杂度为O（EV 3. )（参考 CLRS手册 用于证明时间复杂性） 这是一个重要的问题，因为它出现在许多实际情况中。例如，在给定流量限制下最大化传输，最大化计算机网络中的数据包流量。 Dinc的最大流算法。
练习： 修改上述实现，使其在O（VE）中运行 2. )时间到了。
参考资料： http://www.stanford.edu/class/cs97si/08-network-flow-problems.pdf 算法导论第三版由Clifford Stein、Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest编写 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
