图论学习 c++Ford-Fulkerson 方法

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      // 包含输入输出流的头文件
#include        // 包含向量容器的头文件
#include         // 包含队列容器的头文件
#include       // 包含INT_MAX定义的头文件
#include       // 包含memset函数的头文件
 
using namespace std;    // 使用标准命名空间
 
class FordFulkerson {
    int V; // 顶点数量
    vectorint>> capacity; // 容量矩阵
    vectorint>> 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; // 初始化最大流量为0
        vector<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 容量 10
    graph.addEdge(0, 2, 5);  // S -> B 容量 5
    graph.addEdge(1, 3, 5);  // A -> C 容量 5
    graph.addEdge(2, 3, 10); // B -> C 容量 10
    graph.addEdge(3, 5, 10); // C -> T 容量 10
    
    int source = 0; // 源点 S
    int sink = 5;   // 汇点 T
    
    // 计算并输出最大流量
    cout << "最大流量: " << graph.maxFlow(source, sink) << endl;
    
    return 0;
}