1 基本概念
Ford-Fulkerson方法建立在网络流理论的基本框架之上。它所处理的问题通常可以抽象为：在带有方向和容量限制的图中，从源点向汇点尽可能多地输送“流量”，并且在整个过程中保持各条边不超过承载上限，同时满足中间节点的守恒条件。要理解这一方法，先要掌握网络流、最大流、残量网络和增广路径等核心概念。
1.1 网络流问题
网络流问题研究的是在图结构中如何合理分配和传递流量。它不仅是图论中的经典主题，也是许多实际建模问题的基础，例如运输、分配和匹配等。
1.1.1 图、源点与汇点
在网络流模型中，图通常是一个有向图。图中的每条有向边表示流量可以传递的方向。模型里会指定两个特殊顶点：源点和汇点。源点是流量的起始位置，汇点则是流量的汇聚位置。流量从源点出发，经由若干中间顶点，最终到达汇点。
这种设置使得问题具有明确的方向性，也便于定义“从哪儿来、到哪儿去”的流动过程。若没有源点和汇点，流的概念往往就会转化为其他更一般的图优化问题。
1.1.2 容量约束与流量守恒
每条边都带有一个容量，表示它能够承载的最大流量。任何分配到该边上的流都不能超过这个上限。除此之外，除了源点和汇点以外的所有顶点都必须满足流量守恒：进入该点的总流量等于流出的总流量。
容量约束保证了流不会“超载”，而守恒条件则保证了流在中间节点不会凭空产生或消失。这两条规则共同构成了合法流的基本定义。
1.2 最大流问题
最大流问题是在所有满足约束的可行流中，寻找从源点到汇点能输送的最大总量。它是网络流理论中最核心的问题之一。
1.2.1 可行流与流值
可行流指的是同时满足容量限制与流量守恒的流。对于任意一个可行流，都可以定义一个流值，通常理解为从源点净输出的总流量，或者等价地看作汇点净接收的总流量。
流值是衡量一个流好坏的直接指标。流值越大，说明网络中被有效利用的通道越多，资源传输能力也越强。
1.2.2 最大流的定义
最大流就是在所有可行流中流值最大的那个流。这个定义看似简单，但求解过程并不直观，因为流量在网络中的分配会受到整体结构的制约，局部增加某条边的流，不一定能提升整体流值。
Ford-Fulkerson方法的目标正是通过逐步改进流的分布，最终逼近并得到最大流。
1.3 残量网络
残量网络是Ford-Fulkerson方法中的关键工具，用来表示在当前流状态下，网络中还可以继续增加多少流量，以及哪些流量可以被撤回或调整。
1.3.1 正向边与反向边
对于原图中的每条边，在残量网络里通常会对应两类信息。正向边表示还可以继续增加的流量空间；反向边则表示可以把已经发送出去的一部分流量退回来，以便重新分配。
反向边并不意味着原图中真的存在相反方向的通道，而是算法为了灵活调整流量而引入的一种抽象表示。这种机制使得增广过程不局限于单纯“加流”，也能在必要时修正先前的选择。
1.3.2 残量容量
残量容量表示在当前流的基础上，某条方向上还能继续通过多少流量。对于正向边，它等于原容量减去当前流量；对于反向边，它通常等于当前已经送出的流量。
残量容量直接决定了路径是否还能继续增广。只要残量容量为正，就说明该方向还有可利用空间。
1.4 增广路径
增广路径是指在残量网络中，从源点到汇点的一条可用路径。沿着这条路径调整流量后，整体流值会增加。
1.4.1 路径的可增广性
一条路径要成为增广路径，必须保证路径上的每条边都具有正的残量容量。只有这样，才可以沿整条路径同时增加流量，而不会在中途遇到容量瓶颈。
增广路径的存在，意味着当前流还不是最优的，因为网络中仍有可利用的输送通道。
1.4.2 瓶颈容量
瓶颈容量是增广路径上所有边残量容量的最小值。它决定了本次增广最多能增加多少流量。由于路径中最“紧”的那一段限制了整体提升幅度，所以瓶颈容量是更新流时的关键参数。
沿路径增广时，所有边都会按瓶颈容量进行调整，从而保证路径上的每一条边都不会超出其可用空间。
2 Ford-Fulkerson方法原理
Ford-Fulkerson方法的核心并不在于某一种固定的搜索技巧，而在于一种反复改进流的思想：只要残量网络中还存在增广路径，就继续沿其增加流量；当再也找不到增广路径时，当前流即达到最大。
2.1 核心思想
该方法的本质是通过局部改进推动整体最优。它每一步都只处理一条增广路径，但这些步骤累积起来会逐渐把流量推向极限。
2.1.1 反复寻找增广路径
算法不断在残量网络中搜索源点到汇点的可行路径。只要找到一条，就说明仍有提升空间。这个过程可以理解为在“尚未用满”的通道里继续挖掘输送能力。
如果搜索失败，表示当前残量网络中已经没有从源点到汇点的正容量通路，算法即可停止。
2.1.2 按瓶颈容量更新流量
一旦找到增广路径，就将路径上的流量统一增加一个瓶颈容量。这样既能最大限度利用这条路径，也能确保所有边的容量约束不被破坏。
更新后，原图中的流分布会改变，同时残量网络也随之更新，为下一轮搜索提供新的状态。
2.2 算法步骤
Ford-Fulkerson方法可以概括为一套循环流程，直到无法继续增广为止。
2.2.1 初始化零流
通常从零流开始，即所有边上的流量都设为0。此时显然满足容量约束和流量守恒，是一个最简单的可行初始状态。
2.2.2 构造残量网络
根据当前流量建立残量网络。残量网络记录了哪些边还能继续加流，以及哪些边能够通过反向边进行回退。
这一结构会随着每次增广不断变化，因此不是静态不变的，而是动态维护的。
2.2.3 选择增广路径
在残量网络中寻找一条从源点到汇点的路径。路径的选择方式并不唯一，不同策略会显著影响算法的效率。
2.2.4 更新流与残量图
计算路径的瓶颈容量，并沿路径调整流量：正向边增加，反向边减少。完成后重新得到新的残量网络。
2.2.5 终止条件
当残量网络中不再存在任何增广路径时，算法结束。此时当前流无法再被提升，因而是最大流。
2.3 正确性直观
Ford-Fulkerson方法之所以有效，在于每一步都确保流是合法的，同时每次增广都严格增加流值。最终无法继续增广时，说明已经没有任何方式可以再把更多流从源点送到汇点。
2.3.1 为什么最终得到最大流
如果残量网络中仍存在从源点到汇点的路径，就意味着当前流还不是极限，因为还有未被利用的输送空间。反之，当所有路径都被堵住时，网络已无法再提升总流量，因此当前流达到最优。
这种直观解释与形式化证明相互对应，是最大流理论中非常经典的思想。
2.3.2 与最小割的关系
最大流与最小割之间存在深刻联系。割可以看作将顶点分成两部分，使源点和汇点分居两侧；割边的总容量给出了流量的上界。Ford-Fulkerson方法最终停止时，对应的残量网络结构实际上揭示了一个饱和的割。
因此，最大流的结果不仅表示“最多能送多少”，也间接说明了网络中最薄弱的限制位置在哪里。
3 具体实现
在实际编程中，Ford-Fulkerson方法通常要落到数据结构与搜索策略的具体实现上。尽管理论框架相同，但不同实现方式在效率和易用性上差异明显。
3.1 路径搜索策略
增广路径的查找方式决定了算法的表现。理论上可以任意选路，但实践中通常会采用更稳定或更高效的搜索方法。
3.1.1 深度优先搜索
深度优先搜索实现简单，适合快速写出基础版本的Ford-Fulkerson算法。它沿着一条路径尽量向前探索，直到到达汇点或走不通为止。
这种方式在某些情况下会导致增广路径选择不够理想，从而使增广次数变多，影响整体效率。
3.1.2 广度优先搜索
广度优先搜索会优先寻找边数较少的路径，因此常用于改进版本中。它不会一味深入某一条路径，而是按层次扩展，较容易找到“较短”的增广路。
在最大流算法体系里，广度优先搜索常与特定策略结合，形成更稳定的时间复杂度保证。
3.1.3 任意增广路径选择
最原始的Ford-Fulkerson方法并不规定必须采用哪种搜索。只要找到一条增广路径，就可以继续。这个“任意性”正是它作为方法框架而非单一算法的体现。
不过，任意选择路径虽然灵活，却可能在某些输入上导致非常差的性能。
3.2 流量更新规则
增广时的流量调整必须严格对应残量网络中的方向，避免破坏流的合法性。
3.2.1 正向边增流
若路径经过原图中的正向边，则该边流量增加瓶颈容量。相应地，这条边在残量网络中的剩余可用容量减少。
3.2.2 反向边退流
若路径经过反向边，则表示要撤回之前已经通过某条正向边送出的部分流量。此时原边上的流量减少，而反向边对应的“可退回空间”也随之变化。
这种退流机制是算法能够修正先前决策的重要原因。
3.3 数据结构设计
高效实现Ford-Fulkerson方法，通常离不开合理的图存储方式与路径记录方式。
3.3.1 邻接表表示
邻接表适合存储稀疏图，也便于遍历一个顶点的所有出边。对于网络流问题，邻接表通常比邻接矩阵更节省空间。
3.3.2 残量边存储
实际代码中常把正向边和反向边成对存储，便于在更新时快速找到对应边。这样可以减少查找成本，也使流量修改更直接。
3.3.3 路径回溯记录
在搜索增广路径的过程中，通常需要记录每个节点的前驱信息，方便在找到汇点后回溯整条路径，并计算瓶颈容量。没有这一步，路径更新会变得非常不方便。
4 理论性质
Ford-Fulkerson方法不仅是一个求解流程，也是一套具有明确数学性质的理论框架。其终止性、复杂度和结果正确性，都是最大流研究中的重要内容。
4.1 可终止性
算法能否结束，取决于容量类型和增广策略。对整数容量而言，它通常具有良好的终止性；而在某些非整数情形下，则可能出现更复杂的行为。
4.1.1 整数容量下的终止保证
当所有容量都是整数时，每次增广至少会使流值增加1，因而流值会按离散步长上升。由于总流量有上界，增广次数必然有限，因此算法一定终止。
这也是Ford-Fulkerson方法最常见、最稳定的使用前提。
4.1.2 非整数容量的潜在问题
如果容量不是整数，尤其当使用不恰当的路径选择方式时，流值可能以越来越小的幅度增加，从而出现难以在有限步内结束的情况。理论上，这会使算法的终止性质变得不那么直接。
因此，实际应用中常更倾向于整数容量模型，或采用具有更强保证的改进算法。
4.2 复杂度分析
Ford-Fulkerson方法的复杂度并不固定，而是与增广次数和每次找路的代价密切相关。
4.2.1 与增广次数相关的复杂度
如果每次增广都只能增加很小的流量，那么总增广次数就可能很多。算法总耗时通常是“每次搜索代价 × 增广次数”的组合结果。
也就是说，这个方法的效率高度依赖于路径选择质量。
4.2.2 不同选路策略的影响
不同的增广路径策略会改变实际复杂度。某些策略能显著减少无效增广，使算法更快接近最优；另一些策略则可能反复在局部区域内调整，导致性能不稳定。
因此，Ford-Fulkerson方法常被视为一套思想基础，而非单纯追求固定复杂度的黑箱算法。
4.3 结果性质
算法最终给出的流不仅是最大流，而且还满足网络流模型中的所有基本约束。
4.3.1 最大流与最小割定理
最大流与最小割定理指出，最大流值等于最小割容量。Ford-Fulkerson方法在终止时所得到的结果，与这一理论结论完全一致。
这一定理使得最大流问题不仅是“求最大值”，也成为理解网络结构瓶颈的重要工具。
4.3.2 流守恒与容量合法性
在整个增广过程中，流量始终不会超过边容量，且中间节点依然保持流量守恒。因此，算法输出的解始终是合法的可行流。
这也是其在工程建模中可直接使用的重要原因。
5 特殊变体与相关算法
Ford-Fulkerson方法本身很灵活，而围绕它发展出的改进算法，进一步提升了稳定性和效率。许多经典最大流算法都可以看作对这一思想的延伸。
5.1 Edmonds-Karp算法
Edmonds-Karp算法是Ford-Fulkerson方法的一个著名具体化版本。它通过固定选择规则改善了理论复杂度表现。
5.1.1 基于最短增广路
该算法总是选择边数最少的增广路径，通常用广度优先搜索实现。由于路径选择更有规律，算法行为比任意选路更稳定。
5.1.2 时间复杂度改进
相较于原始Ford-Fulkerson方法，Edmonds-Karp算法能够给出更明确的多项式时间上界，因此在理论分析和教学中都非常常见。
5.2 容量缩放方法
容量缩放是一种通过逐步处理不同规模容量来提升效率的技巧。它把问题分阶段解决，先关注“大流量”部分，再逐渐细化。
5.2.1 分阶段增广
在每个阶段中，只考虑满足某个容量阈值的增广路径。随着阈值降低，算法逐步处理更细小的流量变化。
5.2.2 提升实际效率
这种方法常能减少无意义的小步增广，使算法在实际运行中更高效，尤其适合容量范围较大的网络。
5.3 与其他最大流算法的比较
Ford-Fulkerson方法是最大流算法家族的基础之一，但并不是唯一主流方案。后续算法在结构与性能上各有特点。
5.3.1 Dinic算法
Dinic算法通过分层图和阻塞流思想，在许多场景下比基础增广路径法更快，尤其适合中等到较大规模的网络。
5.3.2 推送-重标号算法
推送-重标号算法采用不同的局部操作机制，不再依赖传统意义上的单条增广路径。它在工程应用中常因较强的性能表现而受到重视。
6 应用
最大流模型用途广泛，Ford-Fulkerson方法因此成为许多组合优化问题的基础工具之一。很多看似不同的问题，经过建模后都能转化为最大流求解。
6.1 二分图匹配
二分图匹配是最大流的经典应用之一，尤其适合把“配对”关系转为“流量传输”关系来处理。
6.1.1 最大匹配到最大流的转化
可以构造一个源点连接左侧顶点、右侧顶点连接汇点的网络，并把匹配关系表示为容量为1的边。这样，最大匹配问题就能转化为最大流问题。
6.1.2 经典建模方式
这种建模方式简单明了，既能求出匹配数量，也能恢复具体匹配方案，因此在算法设计课程中非常常见。
6.2 资源分配问题
当多个任务需要共享有限资源时，最大流模型能够清晰描述“供给—需求—约束”的关系。
6.2.1 任务与容量分配
任务可以看作需要消耗资源的节点，资源点之间的连接则表示可分配关系。容量限制对应资源上限，流量守恒则对应分配平衡。
6.2.2 运输与调度场景
在运输、排班、生产调度等场景中，最大流常用于判断系统是否能在既定限制下完成目标任务，或者找出最大可执行规模。
6.3 计算机科学中的典型用途
最大流不仅是一类数学问题，也经常作为底层建模工具出现在各种计算机科学任务中。
6.3.1 赛程安排
某些赛程安排问题可以转化为网络流。例如，在满足每轮、每队、每场次限制的前提下分配比赛，常能借助最大流构造可行解。
6.3.2 可行性检测
网络流也常用于检测某些约束系统是否存在解。若能找到满足条件的流，就表示方案可行；若最大流不足，则说明约束过紧，无法同时满足所有要求。
7 历史与发展
Ford-Fulkerson方法在网络流理论发展史上占有重要位置。它不仅提出了一个实用的求解框架，也影响了后来一系列更高效算法的产生。
7.1 Ford与Fulkerson的提出
该方法由Ford与Fulkerson提出，是最大流理论早期发展的关键成果之一。
7.1.1 算法思想的形成
他们将“不断寻找增广路径并改进当前流”的思想系统化，使最大流问题从抽象的优化命题变成了可操作的算法流程。
7.1.2 早期影响
这一方法很快成为网络流研究的基础范式。后续许多最大流算法、最小割理论和相关应用，都建立在这一框架之上。
7.2 后续改进
随着研究深入，人们逐渐认识到原始方法在复杂度分析和实现细节上还有进一步优化空间。
7.2.1 复杂度分析的完善
后来学者对其终止性、多项式性以及选路策略影响进行了更系统的分析，使这一方法的理论边界更加清晰。
7.2.2 经典教材中的地位
由于概念直观、建模能力强、理论联系紧密，Ford-Fulkerson方法长期被作为最大流问题的入门核心内容，广泛出现在算法与图论教材中。