《算法導論》對最大流的介紹是：最大流問題是關于流網絡的最簡單的問題，它提出這樣的問題：在不違背容量限制的條件下，把物質從源點傳輸到彙點的最大速率是多少？
更多關于網絡流的介紹請看網絡流wiki
我最初接觸最大流問題是在2011年，那時候我大四，剛保研完，去問導師我需要看哪些方面的書，老闆說去把《算法導論》圖論相關，以及把最大流最小割算法仔細看一遍。
圖論算法在衆多算法中算是比較複雜的了，首先讀入資料需要建構鄰接矩陣，然後再進行求解，求解過程顯得并不是很直覺。當時我對最大流最小割算法本身就不是很明了，更不明白如何可以應用到圖像分割中，現在終于有些體會。
最大流算法
從算法導論書中，最大流算法分為兩種：
Ford-Fulkerson方法：書上對該“方法”進行了解釋，之是以稱作“方法”而不是“算法”，是因為Ford-Fulkerson方法是一種思想，而對這思想的實作，有不同的優化方法
Dinic算法時間複雜度為：$O(n^2m)$，其中n為頂點數，m為邊數
壓入重标記方法(push-relabel)：這同樣也是一種思想，具體實作也有不同的優化實作方法。
H_PRF時間複雜度為(最壞)$O(n^2\sqrt{m})$
Q_PRF時間複雜度為(最壞)$O(n^3)$
最大流=>最小割
決定最大流算法能夠應用在圖像分割的原因，就在于這條定理了
割的定義：
流網絡$G=(V,E)$的割$(S,T)$将$V$劃分為$S$和$T=V-S$兩部分，使得$ s\in{S},t\in{T} $。如果$f$是一個流，則穿過割$(S,T)$的淨流被定義為$f(S,T)$，割$(S,T)$的容量為$c(S,T)$。一個網絡的最小割也就是網絡中所有割中具有最小容量的割。
最大流最小割定理
如果$f$是具有源點$s$和彙點$t$的流網絡$G=(V,E)$中的一個流，則下列條件是等價的：
$f$是$G$的一個最大流
殘留網絡$Gf$不包含增廣路徑
對于$G$的某個割$(S,T)$，有$f=c(S,T)$
其中第三條，說明最大流的值實際上等于某一最小割的容量，即可以用最大流來求取最小割：
$$|f|=f(S,T)=\sum{u\in{S}}\sum{v\in{T}}f(u,v)\leq\sum{u\in{S}}\sum{v\in{T}}c(u,v)$$
為何可以用最小割算法來分割圖像？
這個問題我剛接觸圖割的時候，就想了很久，剛開始我在直覺上比較難了解
首先，要了解，最大流算法得到的最小割有什麼意義？如果寫過最大流算法，或者看明白最大流算法的都知道，在一個增廣路徑中，限制流容量增加的，就是其中具有最小流量的路徑，如果将流從$S$向$T$推送，最終将形成由“最小容量”的一個割，這個割就是最小割，由這些“最小容量”的容量加起來即為最大流(實際上稱作最大淨流好些)
其次，圖像是可以看作由一個個像素組成的巨大圖，假設我将像素一一用邊連接配接起來，則這些像素點會成為這個巨大圖網絡的頂點，如果能利用最大流算法，求取其最小割，通過最小割分開的頂點就是邊權值相對較小的點，假設我邊的權值與頂點間的相似度成正比，那麼最小割分開的頂點就是相似度最小的點，即，通過最大流算法，我們将圖像分成了一塊塊相似的像素區，這不就是圖像分割嗎？
最後，那麼從源點能流出多少流呢？從彙點又能接收多少流呢？如果都是無窮大，那還會形成分割嗎？顯然這是需要限制的。如果從像素點中選出兩個點，一個作為源點，一個作為彙點，圖像中其它點與源點的相似度作為流入的流量，與彙點的相似度作為流出的流量，則應用最大流算法得到的結果，即将點分為兩部分，一部分屬于“相似于”源點，一部分“相似于”彙點，而又由于像素點兩兩相連，為保證像素間的光滑性，會産生相對光滑的分界。
實際中，像素點連接配接源點或彙點的邊叫做T-Link、像素點互相連接配接的邊叫做N-Link、T-link的構造當然要比上述我說的要複雜，而N-Link也不要求要兩兩相連，T-Link限制了像素點與給頂點的相似性，而N-Link限制了像素點之間的光滑性。
在Paper中，對構圖的描述方式不一樣，一般描述為目标函數為一個能量函數，而這個能量函數的優化，可以轉化為一個最小割方法來求解。
Min-Cut/Max-Flow
講到最大流最小割算法，不得不提到大名鼎鼎的Boykov和Kolmogorov，這兩位牛人在2004年圖像領域最頂級雜志TPAMI的一篇文章：An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision，講述了如何将圖像分割轉化為一個能量函數優化問題，并且如何用最大流最小割算法對其進行優化，此外，他們提供了開源的代碼庫，提供了非常友好的接口給相關研究者調用，進而使得基于圖割的圖像分割思想廣泛應用，其中包括後來大名鼎鼎的Lazy Snapping和Grab Cut。像Photoshop，美圖秀秀等基于互動式分割得到目标的功能基本源于圖割方法。
圖割方法在之前的圖像分割領域并非沒有用過，之是以後來應用廣泛，我認為很大一部分原因得益于開源代碼庫：實作一個最大流算法并非特别難的事，但如何高效實作，以及由于圖像像素點很多，如何有效管理實作過程中的記憶體配置設定，及如何提供一個簡單易用的接口，恐怕是絕大部分之前的人研究遇到的難點。
Boykov和Kolmogorov在文章中提出的maxflow算法是一種增廣路徑算法，其方法的時間複雜度為$O(n^2m|C|)$。從理論上講，其時間複雜度大于以上三種，但實際的表現效果，優于以上所有(我猜應該是與圖像所構成的圖的特殊結構有關)。
算法可分為三個步驟：
“growth” stage: search trees S and T grow until they touch giving an s → t path
“augmentation” stage: the found path is augmented, search tree(s) break into forest(s)
“adoption” stage: trees S and T are restored.
僞代碼
1
2
3
4
5
6
7initialize: S = {s}, T = {t}, A = {s, t}, O = ∅
while true
grow S or T to find an augmenting path P from s to t
if P = ∅ terminate
augment on P
adopt orphans
end while
步驟分為三步，基本與增廣路徑算法一緻，其從S和T分别開始搜尋，實際就是雙向廣搜，分别維持着一個屬于S的隊列和一個屬于T的隊列，當S的隊列找到下一個節點，并發現下一個節點屬于T的隊列時，進行增廣，并記錄瓶頸流(bottleneck flow)所在位置，由于這些瓶頸流在增廣後被移除，變為0後，需要重新看還有否必要将這些節點放入到隊列中，這一步叫做adoption。名字還挺不錯:)
具體可見代碼實作，由于其給出的庫是由Template方式編寫，而且用了一些自己定義資料結構，是以代碼不易看懂，需要耐心體會。