网络流算法详解（从零开始掌握C++实现的最大流问题）

核心概念

• 源点（Source）：流量的起点，通常标记为 S。
• 汇点（Sink）：流量的终点，通常标记为 T。
• 容量（Capacity）：每条边能承载的最大流量。
• 残量网络（Residual Network）：表示还能增加多少流量的“剩余空间”。

Ford-Fulkerson 算法原理

Ford-Fulkerson算法是一种求解最大流的经典方法。它的基本思想是：

1. 在残量网络中寻找一条从源点到汇点的路径（称为增广路径）。
2. 找出这条路径上最小的剩余容量（即瓶颈）。
3. 将该路径上的每条边的流量增加这个瓶颈值，并更新残量网络。
4. 重复上述过程，直到找不到增广路径为止。

当无法再找到增广路径时，当前的总流量就是最大流。

C++ 实现步骤

我们将使用邻接表来表示图，并用深度优先搜索（DFS）寻找增广路径。

1. 数据结构定义

// 表示一条边的信息struct Edge {    int to;          // 目标节点    int capacity;    // 容量    int revIndex;    // 反向边在邻接表中的索引};vector<vector<Edge>> graph; // 邻接表

2. 添加边（正向 + 反向）

void addEdge(int from, int to, int cap) {    graph[from].push_back({to, cap, (int)graph[to].size()});    graph[to].push_back({from, 0, (int)graph[from].size() - 1});}

注意：我们同时添加反向边，初始容量为0。这是为了在后续调整流量时能“撤销”操作。

3. DFS 寻找增广路径

int dfs(int u, int t, int flow, vector<bool>& visited) {    if (u == t) return flow;    visited[u] = true;        for (auto& e : graph[u]) {        if (!visited[e.to] && e.capacity > 0) {            int f = dfs(e.to, t, min(flow, e.capacity), visited);            if (f > 0) {                e.capacity -= f;                graph[e.to][e.revIndex].capacity += f;                return f;            }        }    }    return 0;}

4. 主函数：计算最大流

int maxFlow(int s, int t) {    int totalFlow = 0;    while (true) {        vector<bool> visited(graph.size(), false);        int flow = dfs(s, t, INT_MAX, visited);        if (flow == 0) break;        totalFlow += flow;    }    return totalFlow;}

完整示例代码

#include <iostream>#include <vector>#include <climits>using namespace std;struct Edge {    int to, capacity, revIndex;};vector<vector<Edge>> graph;void addEdge(int from, int to, int cap) {    graph[from].push_back({to, cap, (int)graph[to].size()});    graph[to].push_back({from, 0, (int)graph[from].size() - 1});}int dfs(int u, int t, int flow, vector<bool>& visited) {    if (u == t) return flow;    visited[u] = true;    for (auto& e : graph[u]) {        if (!visited[e.to] && e.capacity > 0) {            int f = dfs(e.to, t, min(flow, e.capacity), visited);            if (f > 0) {                e.capacity -= f;                graph[e.to][e.revIndex].capacity += f;                return f;            }        }    }    return 0;}int maxFlow(int s, int t) {    int total = 0;    while (true) {        vector<bool> visited(graph.size(), false);        int f = dfs(s, t, INT_MAX, visited);        if (f == 0) break;        total += f;    }    return total;}int main() {    int n = 6; // 节点数（0~5，其中0为源点，5为汇点）    graph.resize(n);        // 构建图（示例）    addEdge(0, 1, 16);    addEdge(0, 2, 13);    addEdge(1, 2, 10);    addEdge(1, 3, 12);    addEdge(2, 1, 4);    addEdge(2, 4, 14);    addEdge(3, 2, 9);    addEdge(3, 5, 20);    addEdge(4, 3, 7);    addEdge(4, 5, 4);        cout << "最大流为: " << maxFlow(0, 5) << endl; // 输出：23    return 0;}

总结

通过本教程，你已经掌握了网络流算法的基本思想和C++实现网络流的核心技巧。Ford-Fulkerson算法虽然简单，但它是理解更高级算法（如Edmonds-Karp、Dinic）的基础。建议你动手运行代码，修改图的结构，观察输出结果，加深理解。

记住：实践是最好的老师！现在就打开你的IDE，尝试解决一个真实的最大流问题吧！