什么是最大流
最大流要解决的问题是从 S 到 T 怎么才能最大地将数据运到另一边。这个“数据”可以是水，或者网络数据包。举个例子
在上面这个图中将数据从 S 运到 T，其中边的权值称为 Capacity 即，在这条边中流动的数据不能超过 Capacity 值，。
这个图很简单，我们很容易就看出来最大流是 5。流动方向为
- S - 1 - T: 2
- S - 1 - 2 - T: 1
- S - 2 - T: 2
那最小割是啥？就是一堆边的集合，这些边权重加起来应该是要等于最大流的值，且这些边都是从 S 那边到 T 这边的。
简单思路
我们先来大概想个方法去找最大流。其实找最大流的简单方法就是一条路一条路试呗，刚好试到上面三条路就发现是最大的了。
但是总有不如意的时候，比如我们先走 S - 1 - 2 - T，用了流 3，那么整个网络可以再尝试的路只剩下这些了：
现在我们就陷入僵局了，没路可以尝试了，最大流就变成了 3，明显错了。正确的做法应该是这次没找到好的可以进行“反悔”操作，回退上一步之类的，然后再去尝试找最大流嘛。这就需要用到残余网络了。
残余网络
残余网络也叫做 Residual Network，它的出现可以使得我们每次找路的时候进行 “反悔” 操作。比如上面走了 S - 1 - 2 - T 后，残余网络是这样的
可以看到正向走了多少，那么就画一条反向边，这条边的权值就等于前面走了多少流。因为现在有边 2 -> 1 了，所以可以找到一条路 S - 2 - 1 - T，用了流 2，再加上前面找的 3，所以最大流是 5。
这就做完了，其中最小割就是集合 {S - 1, S - 2}: 5。这里所找的路叫做 Augmenting path，反正就是 path，不用去管前面那个是什么意思。
Ford-Fulkerson 算法
画图好画，那程序上怎么实现呢？其实程序上我觉得更容易。伪代码如下
- 首先初始化 Residual Network G
- 使用 DFS 或者 BFS 去找 Augmenting Path，找到一个就加入到 Residual Network G
- 因为使用了之后边是反过来的，所以总会出现 S 走不到 T 的时候，那个时候就停止算法即可
网友评论