福特-福克森算法：寻找增广路径实现最大流

本文主要介绍了广搜（BFS）在寻找增广路径过程中的应用，以及如何通过最大流算法来解决网络流问题。最大流问题是一个经典的问题，它关注的是在一个有向图中，从指定的源点S向目标点T输送最大量的流量，同时确保每个节点的流量进出平衡。在图G=(V,E,C)中，每个边(u,v)都有一个容量c(u,v)，流量f(u,v)需满足0<=f(u,v)<=c(u,v)。 算法的核心步骤包括： 1. 初始化：将所有节点标记为未访问（open=0, closed=1），将源点S的前驱设置为0，并将其放入广搜队列a中。 2. 广度优先搜索（BFS）循环： - 当open小于closed时，遍历广搜队列a，找到一条带有多余流量的边(u,v)，即f[u, v] > 0。 - 更新当前节点的前驱（b[i]=k）和广搜队列（a[closed]=i），如果发现到达了目标节点T，则找到了一条增广路径，算法返回true。 - 若没有找到增广路径，继续搜索。 3. 增广路径： - 一条增广路径是一条从源点S到目标点T的简单路径，其中正向边流量小于其容量，逆向边存在但流量大于0。 - 每找到一条增广路径，沿着该路径更新流量，直到无更多增广路径可用。 4. Ford-Fulkerson算法： - 该算法的核心是重复寻找增广路径并更新流量，直到无法再找到增广路径为止。这个过程中，流量可能不止一个，但每次更新后都会找到一个新的最大值。 5. 最大流的定义： - 网络流图必须包含一个唯一的源点S和一个唯一的汇点T，每条边都有一个非负容量，并且流量满足特定条件，即每个节点的流量流入等于流出。 通过这个过程，我们可以确定给定网络中从S到T的最大流量。在实际应用中，最大流算法被广泛用于各种场景，如网络设计、运输问题、电路设计等，是计算机科学中解决优化问题的重要工具。最小费用最大流和最大流最小割定理也是相关概念，前者考虑的是在满足最大流的前提下，使得总成本最低；后者则揭示了最大流和图中割的等价关系，为理解算法的性质提供了理论支持。