深入理解C语言最大流算法（从零开始掌握网络流核心思想）

常用算法简介

解决最大流问题的经典方法主要有两种：

• Ford-Fulkerson方法：一种基于“增广路径”思想的通用框架。
• Edmonds-Karp算法：Ford-Fulkerson 的具体实现，使用 BFS（广度优先搜索）寻找最短增广路径，保证多项式时间复杂度。

本文将重点讲解 Edmonds-Karp算法，因为它稳定、高效，且易于用 C 语言实现。

算法核心思想

1. 初始化所有边的流量为 0。
2. 在残量网络中，用 BFS 找一条从源点到汇点的路径（称为增广路径）。
3. 找出该路径上最小的剩余容量（即这条路径还能增加多少流量）。
4. 沿着这条路径增加流量，并更新残量网络。
5. 重复步骤 2~4，直到找不到增广路径为止。

残量网络是什么？简单说，就是记录每条边还能“容纳”多少额外流量的图。对于原图中的一条边 (u, v) 容量为 c，若当前流量为 f，则残量网络中存在：
- 正向边 (u, v)，剩余容量 = c - f
- 反向边 (v, u)，剩余容量 = f（用于“撤销”之前流过的流量）

C语言实现 Edmonds-Karp 算法

下面是一个完整的 C 语言实现，包含详细注释，适合初学者理解：

#include <stdio.h>#include <stdlib.h>#include <limits.h>#define MAX_V 100  // 最大顶点数int capacity[MAX_V][MAX_V];  // 容量矩阵int flow[MAX_V][MAX_V];      // 流量矩阵int parent[MAX_V];           // BFS 中记录路径int visited[MAX_V];// 使用 BFS 寻找增广路径，返回路径上的最小剩余容量int bfs(int source, int sink, int n) {    for (int i = 0; i < n; i++) {        visited[i] = 0;        parent[i] = -1;    }        int queue[MAX_V], front = 0, rear = 0;    queue[rear++] = source;    visited[source] = 1;    parent[source] = -1;        while (front < rear) {        int u = queue[front++];        for (int v = 0; v < n; v++) {            // 如果未访问且还有剩余容量            if (!visited[v] && capacity[u][v] - flow[u][v] > 0) {                queue[rear++] = v;                parent[v] = u;                visited[v] = 1;                if (v == sink) {                    // 找到汇点，计算最小剩余容量                    int min_flow = INT_MAX;                    int cur = sink;                    while (cur != source) {                        int prev = parent[cur];                        min_flow = (min_flow < capacity[prev][cur] - flow[prev][cur]) ?                                     min_flow : capacity[prev][cur] - flow[prev][cur];                        cur = prev;                    }                    return min_flow;                }            }        }    }    return 0;  // 未找到增广路径}// Edmonds-Karp 主函数int edmonds_karp(int source, int sink, int n) {    // 初始化流量为0    for (int i = 0; i < n; i++)        for (int j = 0; j < n; j++)            flow[i][j] = 0;        int max_flow = 0;    int path_flow;        // 不断寻找增广路径    while ((path_flow = bfs(source, sink, n)) != 0) {        max_flow += path_flow;        // 更新残量网络        int cur = sink;        while (cur != source) {            int prev = parent[cur];            flow[prev][cur] += path_flow;   // 正向边增加流量            flow[cur][prev] -= path_flow;   // 反向边减少流量（等价于增加反向容量）            cur = prev;        }    }        return max_flow;}// 示例主函数int main() {    int n = 4;  // 顶点数：0=源点, 3=汇点    // 构建容量图    capacity[0][1] = 10;    capacity[0][2] = 5;    capacity[1][2] = 15;    capacity[1][3] = 10;    capacity[2][3] = 10;        int source = 0, sink = 3;    int result = edmonds_karp(source, sink, n);    printf("最大流为: %d\n", result);    return 0;}  

代码说明

- capacity[u][v] 存储原始图中边 (u, v) 的容量。
- flow[u][v] 记录当前从 u 到 v 的流量。
- BFS 函数不仅判断是否存在路径，还返回该路径能增加的最大流量。
- 每次找到路径后，沿路径更新正向和反向边的流量，这是Ford-Fulkerson方法的关键技巧。

时间复杂度与优化

Edmonds-Karp 算法的时间复杂度为 O(V·E²)，其中 V 是顶点数，E 是边数。虽然不是最快的（Dinic 算法更快），但它实现简单、稳定可靠，非常适合学习和中小规模问题。

总结

通过本文，你已经掌握了 C语言最大流算法 的基本原理和实现方法。无论是理解网络流算法的核心思想，还是动手编写 Edmonds-Karp算法 或 Ford-Fulkerson方法，你都迈出了坚实的一步。建议你尝试修改示例图、添加更多边，观察输出结果，加深理解。

记住：算法学习贵在实践。动手写代码、调试、思考，才是掌握最大流这类经典问题的最佳途径！