Ford-Fulkerson算法是用于求解最大流問題的一種經典算法。其核心思想是通過不斷尋找增廣路徑來增加流量，直到找不到增廣路徑為止。每次找到一條增廣路徑，就增加相應的流量，更新殘余網絡。簡單來說就是Ford-Fulkerson算法的工作過程，即不斷尋找增廣路徑并增加流量，直到無法找到增廣路徑為止。

算法步驟

1. 初始化： 將所有邊的流量初始化為0。
2. 尋找增廣路徑： 使用深度優先搜索（DFS）或廣度優先搜索（BFS）在殘余網絡中尋找從源點到匯點的增廣路徑。
3. 增廣路徑上增加流量： 在找到的增廣路徑上增加可以增加的最小流量。
4. 更新殘余網絡： 根據增廣路徑上的流量調整殘余網絡。
5. 重復步驟2-4，直到找不到增廣路徑為止。

以一個簡單的例子來演示Ford-Fulkerson算法的執行過程。

假設有一個流網絡如下：

  源點 (S)/   \
10     5
/       \
A        B
\       /5   10\   /C|10|匯點 (T)

其中每條邊的數字表示容量。

步驟1：初始化

• 所有邊的流量初始化為0。

步驟2：尋找增廣路徑

• 使用DFS或BFS從源點S尋找增廣路徑。假設我們使用DFS找到路徑S -> A -> C -> T，路徑上的容量為10，最小容量為5。

步驟3：增廣路徑上增加流量

• 增加流量5。路徑S -> A -> C -> T上各邊的流量增加5。
• 更新后的流量：
  • S -> A 流量為5，剩余容量為5。
  • A -> C 流量為5，剩余容量為0。
  • C -> T 流量為5，剩余容量為5。

步驟4：更新殘余網絡

• 根據增廣路徑上的流量調整殘余網絡。增加逆向邊用于表示可以回退的流量。
  • 增加逆向邊A -> S，容量為5，流量為0。
  • 增加逆向邊C -> A，容量為5，流量為0。
  • 增加逆向邊T -> C，容量為5，流量為0。

步驟2：尋找增廣路徑（繼續）

• 繼續尋找另一條增廣路徑。假設找到路徑S -> B -> C -> T，路徑上的容量為10，最小容量為5。

步驟3：增廣路徑上增加流量

• 增加流量5。路徑S -> B -> C -> T上各邊的流量增加5。
• 更新后的流量：
  • S -> B 流量為5，剩余容量為0。
  • B -> C 流量為5，剩余容量為5。
  • C -> T 流量為10，剩余容量為0。

步驟4：更新殘余網絡

• 根據增廣路徑上的流量調整殘余網絡。增加逆向邊用于表示可以回退的流量。
  • 增加逆向邊B -> S，容量為5，流量為0。
  • 增加逆向邊C -> B，容量為5，流量為0。
  • 增加逆向邊T -> C，容量為5，流量為0。

步驟2：尋找增廣路徑（結束）

• 繼續尋找增廣路徑，發現沒有增廣路徑了。

結果

• 最大流量為10。

#include <iostream>     // 包含輸入輸出流的頭文件
#include <vector>       // 包含向量容器的頭文件
#include <queue>        // 包含隊列容器的頭文件
#include <climits>      // 包含INT_MAX定義的頭文件
#include <cstring>      // 包含memset函數的頭文件using namespace std;    // 使用標準命名空間class FordFulkerson {int V; // 頂點數量vector<vector<int>> capacity; // 容量矩陣vector<vector<int>> adj; // 鄰接表// 廣度優先搜索(BFS)函數，用于在殘余網絡中尋找增廣路徑bool bfs(vector<int>& parent, int s, int t) {vector<bool> visited(V, false); // 訪問標記數組，初始化為未訪問queue<int> q; // BFS隊列q.push(s); // 源點入隊visited[s] = true; // 標記源點為已訪問parent[s] = -1; // 源點沒有父節點while (!q.empty()) { // 當隊列不為空時int u = q.front(); // 取出隊首元素q.pop(); // 隊首元素出隊for (int v : adj[u]) { // 遍歷鄰接表中的所有鄰接節點if (!visited[v] && capacity[u][v] > 0) { // 如果節點未訪問且有剩余容量if (v == t) { // 如果找到匯點parent[v] = u; // 記錄父節點return true; // 返回找到增廣路徑}q.push(v); // 將節點入隊parent[v] = u; // 記錄父節點visited[v] = true; // 標記節點為已訪問}}}return false; // 如果沒有找到增廣路徑，返回false}public:// 構造函數，初始化頂點數量、容量矩陣和鄰接表FordFulkerson(int V) : V(V), capacity(V, vector<int>(V, 0)), adj(V) {}// 添加邊及其容量void addEdge(int u, int v, int cap) {capacity[u][v] = cap; // 設置容量adj[u].push_back(v); // 添加鄰接點adj[v].push_back(u); // 添加反向邊的鄰接點}// 計算最大流量int maxFlow(int s, int t) {int max_flow = 0; // 初始化最大流量為0vector<int> parent(V); // 用于記錄增廣路徑中的父節點while (bfs(parent, s, t)) { // 當找到增廣路徑時int path_flow = INT_MAX; // 初始化路徑流量為無窮大// 計算增廣路徑中的最小流量for (int v = t; v != s; v = parent[v]) {int u = parent[v];path_flow = min(path_flow, capacity[u][v]);}// 更新殘余網絡中的容量for (int v = t; v != s; v = parent[v]) {int u = parent[v];capacity[u][v] -= path_flow;capacity[v][u] += path_flow;}// 增加總流量max_flow += path_flow;}return max_flow; // 返回最大流量}
};int main() {int V = 6; // 頂點數量 (包括源點和匯點)FordFulkerson graph(V); // 創建一個FordFulkerson對象// 添加邊和對應的容量graph.addEdge(0, 1, 10); // S -> A 容量 10graph.addEdge(0, 2, 5);  // S -> B 容量 5graph.addEdge(1, 3, 5);  // A -> C 容量 5graph.addEdge(2, 3, 10); // B -> C 容量 10graph.addEdge(3, 5, 10); // C -> T 容量 10int source = 0; // 源點 Sint sink = 5;   // 匯點 T// 計算并輸出最大流量cout << "最大流量: " << graph.maxFlow(source, sink) << endl;return 0;
}