Ford-Fulkerson 算法 · Programiz 中文系列教程

# Ford-Fulkerson 算法 > 原文： [https://www.programiz.com/dsa/ford-fulkerson-algorithm](https://www.programiz.com/dsa/ford-fulkerson-algorithm) #### 在本教程中，您將學習什么是 Ford-Fulkerson 算法。此外，您還將找到在 C，C++ ，Java 和 Python 中找到流網絡中最大流的工作示例。 Ford-Fulkerson 算法是一種[貪婪方法](http://programiz.com/dsa/greedy-algorithm)，用于計算網絡或圖形中的最大可能流量。術語**網絡流**用于描述具有源（`S`）和宿（`T`）的頂點和邊的網絡。除了`S`和`T`之外，每個頂點都可以通過它接收和發送相同數量的東西。 `S`只能發送，`T`只能接收東西。我們可以使用不同容量的管網內部的液體流動來可視化對算法的理解。每個管道在特定情況下都可以傳輸一定容量的液體。對于此算法，我們將查找使用網絡在實例處可以從源流向水槽的液體量。 ![Flow network](https://img.kancloud.cn/0f/1d/0f1dedf4fead611fcf66909d5b7508d6_798x358.png "Flow network") 圖的網絡流 * * * ## 使用的術語 ### 增廣路徑它是流網絡中可用的路徑。 ### 剩余圖它表示具有其他可能流量的網絡流。 ### 剩余容量從最大容量中減去流量后的邊容量。 * * * ## Ford-Fulkerson 算法如何工作？該算法如下： 1. 將所有邊中的流初始化為 0。 2. 當源和接收器之間存在增加路徑時，將此路徑添加到流中。 3. 更新剩余圖。如果需要，我們還可以考慮反向路徑，因為如果不考慮反向路徑，則可能永遠找不到最大流量。通過以下示例可以理解上述概念。 * * * ## Ford-Fulkerson 的例子開始時所有邊的流為 0。 ![Flow network](https://img.kancloud.cn/63/fd/63fdddfc04021a73e4ab10dc980fc748_608x358.png "Flow network") 圖的網絡流示例 1. 選擇從`S`到`T`的任意路徑。在此步驟中，我們選擇了路徑`S-A-B-T`。 ![Find a path](https://img.kancloud.cn/bd/bc/bdbc00fb771921357b9f5a11bce8218e_608x358.png "Find a path") 找到路徑三個邊之間的最小容量為 2（`B-T`）。基于此，為每個路徑更新流量/容量。 ![Update the capacities](https://img.kancloud.cn/c7/bb/c7bb59a1a21cf0b13841940f03c67d59_608x358.png "Update the capacities") 更新容量 2. 選擇其他路徑`S-D-C-T`。這些邊之間的最小容量為 3（`S-D`）。 ![Find next path](https://img.kancloud.cn/c9/2c/c92cb7708fb86beb96dde486db43fc92_608x358.png "Find next path") 查找下一個路徑根據此更新容量。 ![Update the capacities](https://img.kancloud.cn/bd/e2/bde23cde85547151d3821f6d4b9a7097_608x358.png "Update the capacities") 更新容量 3. 現在，讓我們考慮反向路徑`B-D`。選擇路徑`S-A-B-D-C-T`。邊之間的最小剩余容量為 1（`D-C`）。 ![Find next path](https://img.kancloud.cn/1f/81/1f81b5b685c96b52385acfc04fbf3765_608x358.png "Find next path") 查找下一個路徑正在更新容量。 ![Update the capacities](https://img.kancloud.cn/3f/b6/3fb66f01a13540dfa49b38baa35bdd07_608x358.png "Update the capacities") 更新容量分別考慮正向和反向路徑的容量。 4. 將所有流量相加，`2 + 3 + 1 = 6`，這是網絡流上的最大可能流量。請注意，如果任何邊的容量已滿，則無法使用該路徑。 * * * ## Python，Java 和 C/C++ 示例 ```py # Ford-Fulkerson algorith in Python from collections import defaultdict class Graph: def __init__(self, graph): self.graph = graph self. ROW = len(graph) # Using BFS as a searching algorithm def searching_algo_BFS(self, s, t, parent): visited = [False] * (self.ROW) queue = [] queue.append(s) visited[s] = True while queue: u = queue.pop(0) for ind, val in enumerate(self.graph[u]): if visited[ind] == False and val > 0: queue.append(ind) visited[ind] = True parent[ind] = u return True if visited[t] else False # Applying fordfulkerson algorithm def ford_fulkerson(self, source, sink): parent = [-1] * (self.ROW) max_flow = 0 while self.searching_algo_BFS(source, sink, parent): path_flow = float("Inf") s = sink while(s != source): path_flow = min(path_flow, self.graph[parent[s]][s]) s = parent[s] # Adding the path flows max_flow += path_flow # Updating the residual values of edges 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 graph = [[0, 8, 0, 0, 3, 0], [0, 0, 9, 0, 0, 0], [0, 0, 0, 0, 7, 2], [0, 0, 0, 0, 0, 5], [0, 0, 7, 4, 0, 0], [0, 0, 0, 0, 0, 0]] g = Graph(graph) source = 0 sink = 5 print("Max Flow: %d " % g.ford_fulkerson(source, sink)) ``` ```java // Ford-Fulkerson algorith in Java import java.util.LinkedList; class FordFulkerson { static final int V = 6; // Using BFS as a searching algorithm boolean bfs(int Graph[][], int s, int t, int p[]) { boolean visited[] = new boolean[V]; for (int i = 0; i < V; ++i) visited[i] = false; LinkedList<Integer> queue = new LinkedList<Integer>(); queue.add(s); visited[s] = true; p[s] = -1; while (queue.size() != 0) { int u = queue.poll(); for (int v = 0; v < V; v++) { if (visited[v] == false && Graph[u][v] > 0) { queue.add(v); p[v] = u; visited[v] = true; } } } return (visited[t] == true); } // Applying fordfulkerson algorithm int fordFulkerson(int graph[][], int s, int t) { int u, v; int Graph[][] = new int[V][V]; for (u = 0; u < V; u++) for (v = 0; v < V; v++) Graph[u][v] = graph[u][v]; int p[] = new int[V]; int max_flow = 0; # Updating the residual calues of edges while (bfs(Graph, s, t, p)) { int path_flow = Integer.MAX_VALUE; for (v = t; v != s; v = p[v]) { u = p[v]; path_flow = Math.min(path_flow, Graph[u][v]); } for (v = t; v != s; v = p[v]) { u = p[v]; Graph[u][v] -= path_flow; Graph[v][u] += path_flow; } // Adding the path flows max_flow += path_flow; } return max_flow; } public static void main(String[] args) throws java.lang.Exception { int graph[][] = new int[][] { { 0, 8, 0, 0, 3, 0 }, { 0, 0, 9, 0, 0, 0 }, { 0, 0, 0, 0, 7, 2 }, { 0, 0, 0, 0, 0, 5 }, { 0, 0, 7, 4, 0, 0 }, { 0, 0, 0, 0, 0, 0 } }; FordFulkerson m = new FordFulkerson(); System.out.println("Max Flow: " + m.fordFulkerson(graph, 0, 5)); } } ``` ```c / Ford - Fulkerson algorith in C #include <stdio.h> #define A 0 #define B 1 #define C 2 #define MAX_NODES 1000 #define O 1000000000 int n; int e; int capacity[MAX_NODES][MAX_NODES]; int flow[MAX_NODES][MAX_NODES]; int color[MAX_NODES]; int pred[MAX_NODES]; int min(int x, int y) { return x < y ? x : y; } int head, tail; int q[MAX_NODES + 2]; void enqueue(int x) { q[tail] = x; tail++; color[x] = B; } int dequeue() { int x = q[head]; head++; color[x] = C; return x; } // Using BFS as a searching algorithm int bfs(int start, int target) { int u, v; for (u = 0; u < n; u++) { color[u] = A; } head = tail = 0; enqueue(start); pred[start] = -1; while (head != tail) { u = dequeue(); for (v = 0; v < n; v++) { if (color[v] == A && capacity[u][v] - flow[u][v] > 0) { enqueue(v); pred[v] = u; } } } return color[target] == C; } // Applying fordfulkerson algorithm int fordFulkerson(int source, int sink) { int i, j, u; int max_flow = 0; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { flow[i][j] = 0; } } // Updating the residual values of edges while (bfs(source, sink)) { int increment = O; for (u = n - 1; pred[u] >= 0; u = pred[u]) { increment = min(increment, capacity[pred[u]][u] - flow[pred[u]][u]); } for (u = n - 1; pred[u] >= 0; u = pred[u]) { flow[pred[u]][u] += increment; flow[u][pred[u]] -= increment; } // Adding the path flows max_flow += increment; } return max_flow; } int main() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { capacity[i][j] = 0; } } n = 6; e = 7; capacity[0][1] = 8; capacity[0][4] = 3; capacity[1][2] = 9; capacity[2][4] = 7; capacity[2][5] = 2; capacity[3][5] = 5; capacity[4][2] = 7; capacity[4][3] = 4; int s = 0, t = 5; printf("Max Flow: %d\n", fordFulkerson(s, t)); } ``` ```cpp // Ford-Fulkerson algorith in C++ #include <limits.h> #include <string.h> #include <iostream> #include <queue> using namespace std; #define V 6 // Using BFS as a searching algorithm bool bfs(int rGraph[V][V], int s, int t, int parent[]) { bool visited[V]; memset(visited, 0, sizeof(visited)); queue<int> q; q.push(s); visited[s] = true; parent[s] = -1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v = 0; v < V; v++) { if (visited[v] == false && rGraph[u][v] > 0) { q.push(v); parent[v] = u; visited[v] = true; } } } return (visited[t] == true); } // Applying fordfulkerson algorithm int fordFulkerson(int graph[V][V], int s, int t) { int u, v; int rGraph[V][V]; for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph[u][v] = graph[u][v]; int parent[V]; int max_flow = 0; // Updating the residual values of edges while (bfs(rGraph, s, t, parent)) { int path_flow = INT_MAX; for (v = t; v != s; v = parent[v]) { u = 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; } // Adding the path flows max_flow += path_flow; } return max_flow; } int main() { int graph[V][V] = {{0, 8, 0, 0, 3, 0}, {0, 0, 9, 0, 0, 0}, {0, 0, 0, 0, 7, 2}, {0, 0, 0, 0, 0, 5}, {0, 0, 7, 4, 0, 0}, {0, 0, 0, 0, 0, 0}}; cout << "Max Flow: " << fordFulkerson(graph, 0, 5) << endl; } ``` * * * ## Ford-Fulkerson 應用 * 輸水管道 * 二分匹配問題 * 按需流動