Python实现最大流算法详解（从零开始掌握网络流算法）

常用的最大流算法

解决最大流问题的经典算法包括 Ford-Fulkerson 算法 和其改进版本 Edmonds-Karp 算法。其中，Ford-Fulkerson 是基础思想，而 Edmonds-Karp 使用广度优先搜索（BFS）来寻找增广路径，保证了算法的时间复杂度为 O(VE²)，更适合实际应用。

在本教程中，我们将重点实现 Edmonds-Karp 算法，因为它更稳定且易于理解。

Python 实现 Edmonds-Karp 最大流算法

我们使用邻接矩阵表示图，并用 BFS 寻找增广路径。以下是完整的 Python 代码：

from collections import dequedef bfs(capacity, source, sink, parent):    """    使用 BFS 寻找从 source 到 sink 的增广路径    如果找到路径，返回 True 并更新 parent 数组    """    visited = [False] * len(capacity)    queue = deque()    queue.append(source)    visited[source] = True    parent[source] = -1    while queue:        u = queue.popleft()        for v in range(len(capacity)):            if not visited[v] and capacity[u][v] > 0:                queue.append(v)                parent[v] = u                visited[v] = True                if v == sink:                    return True    return Falsedef edmonds_karp(capacity, source, sink):    """    Edmonds-Karp 算法实现最大流    :param capacity: 容量矩阵（二维列表）    :param source: 源点索引    :param sink: 汇点索引    :return: 最大流值    """    n = len(capacity)    residual_capacity = [row[:] for row in capacity]  # 残量图    parent = [-1] * n    max_flow = 0    # 不断寻找增广路径    while bfs(residual_capacity, source, sink, parent):        # 找到路径上的最小残量        path_flow = float('Inf')        s = sink        while s != source:            path_flow = min(path_flow, residual_capacity[parent[s]][s])            s = parent[s]        # 更新残量图        v = sink        while v != source:            u = parent[v]            residual_capacity[u][v] -= path_flow            residual_capacity[v][u] += path_flow  # 反向边            v = parent[v]        max_flow += path_flow    return max_flow# 示例：构建一个简单的网络if __name__ == "__main__":    # 节点数量：0=源点, 1,2=中间节点, 3=汇点    graph = [        [0, 16, 13, 0],   # 0 -> 1 (16), 0 -> 2 (13)        [0, 0, 10, 12],   # 1 -> 2 (10), 1 -> 3 (12)        [0, 4, 0, 14],    # 2 -> 1 (4), 2 -> 3 (14)        [0, 0, 0, 0]      # 汇点无出边    ]    source = 0    sink = 3    result = edmonds_karp(graph, source, sink)    print(f"最大流为: {result}")

代码说明

• bfs 函数：用于在残量图中寻找一条从源点到汇点的路径。如果找到，就记录路径（通过 parent 数组）。
• edmonds_karp 函数：主函数，不断调用 BFS 寻找增广路径，并更新残量图，直到找不到新路径为止。
• 残量图（Residual Graph）：记录每条边剩余的容量，同时维护反向边以支持“撤销”操作。

运行上述代码，输出结果为：

最大流为: 23

为什么选择 Edmonds-Karp？

相比原始的 Ford-Fulkerson 算法（可能因 DFS 选择路径不当导致无限循环或效率低下），Edmonds-Karp 算法使用 BFS 总是选择最短的增广路径，从而保证了多项式时间复杂度，是实际工程中更可靠的选择。

总结

通过本教程，你已经掌握了如何用 Python 实现最大流算法，特别是 Edmonds-Karp 算法。这项技能在解决物流、通信、匹配等问题时非常有用。建议你尝试修改图的结构，观察最大流的变化，加深理解。

记住，网络流算法实现的核心在于理解残量图和增广路径的概念。多练习，你就能灵活运用这些算法解决实际问题！