什么是最大流
最大流要解決的問題是從 S 到 T 怎么才能最大地將數(shù)據(jù)運到另一邊。這個“數(shù)據(jù)”可以是水，或者網(wǎng)絡數(shù)據(jù)包。舉個例子
在上面這個圖中將數(shù)據(jù)從 S 運到 T，其中邊的權值稱為 Capacity 即，在這條邊中流動的數(shù)據(jù)不能超過 Capacity 值，。
這個圖很簡單，我們很容易就看出來最大流是 5。流動方向為
- S - 1 - T: 2
- S - 1 - 2 - T: 1
- S - 2 - T: 2
那最小割是啥？就是一堆邊的集合，這些邊權重加起來應該是要等于最大流的值，且這些邊都是從 S 那邊到 T 這邊的。
簡單思路
我們先來大概想個方法去找最大流。其實找最大流的簡單方法就是一條路一條路試唄，剛好試到上面三條路就發(fā)現(xiàn)是最大的了。
但是總有不如意的時候，比如我們先走 S - 1 - 2 - T，用了流 3，那么整個網(wǎng)絡可以再嘗試的路只剩下這些了：
現(xiàn)在我們就陷入僵局了，沒路可以嘗試了，最大流就變成了 3，明顯錯了。正確的做法應該是這次沒找到好的可以進行“反悔”操作，回退上一步之類的，然后再去嘗試找最大流嘛。這就需要用到殘余網(wǎng)絡了。
殘余網(wǎng)絡
殘余網(wǎng)絡也叫做 Residual Network，它的出現(xiàn)可以使得我們每次找路的時候進行 “反悔” 操作。比如上面走了 S - 1 - 2 - T 后，殘余網(wǎng)絡是這樣的
可以看到正向走了多少，那么就畫一條反向邊，這條邊的權值就等于前面走了多少流。因為現(xiàn)在有邊 2 -> 1 了，所以可以找到一條路 S - 2 - 1 - T，用了流 2，再加上前面找的 3，所以最大流是 5。
這就做完了，其中最小割就是集合 {S - 1, S - 2}: 5。這里所找的路叫做 Augmenting path，反正就是 path，不用去管前面那個是什么意思。
Ford-Fulkerson 算法
畫圖好畫，那程序上怎么實現(xiàn)呢？其實程序上我覺得更容易。偽代碼如下
- 首先初始化 Residual Network G
- 使用 DFS 或者 BFS 去找 Augmenting Path，找到一個就加入到 Residual Network G
- 因為使用了之后邊是反過來的，所以總會出現(xiàn) S 走不到 T 的時候，那個時候就停止算法即可
