什么是最大流问题？
最大流也就是Max Flow问题可能对很多学习算法理论的人比较陌生，它不如贪心算法，分治算法，动态规划这么出名，但是很多算法问题都可以被归约为最大流问题，最大流问题有着相当广的适应面和应用度。先来看一下以下的最大流问题
我们可以看到上图中有s, v, t, w四个不同的节点，图中有5条不同的连接两个节点的边，每一条边上面都有一个数字，注意这个数字代表的并不是我们一般在路径算法图中遇到的路径的权重，这个数字代表的是这条边能够承受的最大流量。s与t是两个特殊的节点，我们把s称作流出点(source)，t称作吸收点(sink)，我们可以将所有的边看作是大小不一的管道，我们的任务就是规划如何将最大的流量从s通过这些管道推流到t点。下面我们来看一下上图的一种解
在上图的解中我们给出了三条流：第一条绿色为s-v-w-t流量为1，第二条红色为s-v-t流量为2，第三条蓝色为s-w-t流量为2。我们得到了流的总和为5。那这个总量为5的流到底是不是所谓的最大流呢？或者我们如何分辨当前的解已经达到最大流呢？我在这里可以告诉你5确实是这个图的最大流，但是关于这两个问题我将在稍后给出解答。在这里我先要澄清的一点是最大流问题可能并不只有单一解，再来看到上图，我们给出第二个解：第一条s-v-w-t流量为3，第二条s-w-v-t流量为2，我们再次得到了流量的总和为5。
福特福克森算法
下面我就来介绍一个很有名的解决最大流的算法——福特福克森（Ford-Fulkerson）算法。这个算法其实相当简单，因为它可以被看作为一种贪心算法，我们来看一下这个算法//1.设置最大流的初始值 f = 0
//2.当「残留图」中还有从「流出点」到「吸收点」的「可扩路径」时，我们将「可扩路径」所含的流量加到 f 中
//3.返回 f
这个算法虽然简短，但是包含了2个全新的概念：残留图（Residual Graph）与可扩路径（Augmenting Path）。这两个名词看似都很厉害，其实都很容易理解，我们下面就来解释一下这两个名词。
残留图
残留图简单的理解就是在我们每次推流后将图改画成另一种等价图的表达方式，这种表达方式并没有改变图的值但是却为反向推流创造了空间，假如日后福特福克森算法在你脑海中淡忘了，但请务必记住这个残留图的概念，因为它是这个算法精髓中的精髓。来看一下下面这个图
在左图中我们看到了v,w两个节点，在两个节点间，Ue是这个边能承受的总流量，Fe是从v往w推送的流量。我们来看这个右图，也就是左图改写后的残留图，我们将边v至w的值改写为Ue-Fe，也就是在推送完了Fe之后你还能从v推往w的总流量；我们往残留图中添加了一条新的边也就是w至v，w至v的值也就是我们刚刚从v推往w的Fe的值。用通俗的话来说就是你往一个方向推了多少流量，你就可以从反方向推流来抵消掉相同的流量。
可扩路径
理解了残留图我们再来理解一下可扩路径，可扩路径简单的说就是一条从流出点到吸收点的可行路径，只是可扩路径并不是在原图中的从s至t的可行路径，而是在残留图中的可行路径。在残留图中，也就是意味着可扩路径在寻路上有了更多的选择，它甚至可以走一个边的反方向。我们来看一个实例来理解一下这个概念
| 推流前 | 推流后 |
|---|---|
 |
 |
还是拿最开始的例子在左图中我们往s-v-w-t推送了值为3的流，右图便是推送完这个流后的残留图，可以观察到s-v与w-t的边方向已经相反了，也就是意味着我们耗尽了正向推流的量，现在只能够反向推流了，而边v-w被分成双向边一条为v至w值为2，一条为w至v值为3。那么现在我们有了残留图，试着来找一下可扩路径。细心的读者可能已经发现了，没错，就是往s-w-v-t推送值为2的流。如果我们不用残留图，我们是不可能从w往v推流的，也正是因为残留图，给了我们抵消正向推流的能力，完美地解决了最大流问题。
如何知道我们已经获得最大流？
这个问题可能有些读者已经急不可耐了，现在我们理解了残留图我们就可以很好地来解释这个问题了。那么这儿有一个显而易见的定理来解释这个问题就是“如果残留图中再也找不到从流出点至吸收点的路径，那么当前你获得的流就是最大流”。
福特福克森的时间复杂度
这个算法的时间复杂度是O(E * f)，E在这里代表的是图中边的数量，而f代表的是图的最大流。简单的说为找到一条可扩路径，我们可能需要利用深度优先搜索（DFS）或广度优先搜索（BFS）走遍图中所有的边，但是可能的是，费尽千辛万苦找到的一条可扩路径只为我们带来了1的流量。可想而知，对于一些有着巨大最大流的图，要是这个算法每次遍历图只能获得值1为的流量的话，那运算效率是极低的。还有一点值得注意的是福特福克森并不是解决最大流的最有效算法（ Dinic的算法为O(VElog(V))，James B Orlin的算法为O(VE) ，V代表图中节点的数量），但却是一种解决此问题的比较通俗易懂，容易实施的算法。
最大流的应用
大约理解了什么是最大流问题与最大流算法后，我们来看一下最大流的应用，最大流的应用有很多，在这里我只举一个比较通俗易懂的例子。来看一下这个问题：在一个大学里有n个学生与m个宿舍，每个学生都想住进自己选择的一些宿舍中的其中一间，每个宿舍最多都只能容纳2位学生，问到底有没有可能达成这种匹配让每个学生都有宿舍住。我们可以把这个问题轻松地转化为最大流的问题。
上图便给出了一个该问题的最大流版本，可以看到我们将n个学生与m个宿舍都做成了图中的节点，并增加了流出点s与吸收点t，从s至学生的边代表了每个学生，所以每条边的值为1；从学生至宿舍代表了学生对宿舍的喜好选择，当一个学生愿意去某一个宿舍时，我们就在这个学生与宿舍之间增加一个值为1的边；从宿舍到t代表了每个宿舍的容纳度所以每条边的值为2。当我们已经将问题归约为最大流问题的时候，要解决这个问题只需要在这个图上使用最大流算法即可。当我们在此图中运行完最大流算法发现最大流 f = n 时说明每个学生都有宿舍住，但如果最大流 f < n 说明学校的宿舍无法满足每个学生的需求，至于 f > n 为什么不存在，这个问题就留给你们思考了。
小结
最大流问题是一个十分具有应用价值的问题，实际应用例如二分图问题(我刚刚介绍的学生与宿舍问题也属于这个范畴)，需求与供给问题等等。这篇文章只是对最大流问题概念的一个简单入门，希望能够帮助到感兴趣的读者们。如果你对最大流问题还有兴趣，可以翻看网上福特福克森算法的Java或者C++实例来进一步加深对这个算法与这个问题的理解。