最大流最小割算法實現(xiàn)方案一、概述

最大流最小割算法是圖論中解決網(wǎng)絡流問題的核心方法，用于在給定網(wǎng)絡中尋找從源點到匯點的最大流量，同時確定相應的最小割集。該算法基于Ford-Fulkerson方法及其變種，通過不斷尋找增廣路徑來迭代增加流量，直至無法再增廣為止。最小割則是將網(wǎng)絡分割為源點和匯點兩部分，且割集容量等于當前最大流量。本方案將詳細介紹該算法的實現(xiàn)步驟、關鍵數(shù)據(jù)結構和優(yōu)化策略。

二、算法實現(xiàn)步驟

最大流最小割算法的實現(xiàn)主要分為以下幾個步驟：

（一）初始化

1.創(chuàng)建網(wǎng)絡圖表示：使用鄰接矩陣或鄰接表存儲邊的容量信息。

2.初始化流量：所有邊的初始流量為0。

3.設置源點和匯點：明確網(wǎng)絡中的起始節(jié)點和結束節(jié)點。

（二）增廣路徑搜索

1.使用深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜索（BFS）尋找從源點到匯點的可增廣路徑。

2.檢查路徑上每條邊的剩余容量，確保路徑有效（即每條邊流量未達到容量上限）。

3.記錄路徑上的最小剩余容量，作為本次增廣的流量調(diào)整值。

（三）流量調(diào)整

1.沿增廣路徑增加流量：將路徑上每條邊的流量增加最小剩余容量值。

2.更新網(wǎng)絡圖：調(diào)整邊的流量，并計算剩余容量（容量-流量）。

3.重復搜索：直至無法找到新的增廣路徑。

（四）最小割確定

1.構建最小割集：通過網(wǎng)絡割分，找到割集容量等于最大流量的分割方式。

2.計算割集容量：匯總割集邊上的原始容量，作為最小割值。

三、關鍵數(shù)據(jù)結構

（一）網(wǎng)絡表示

1.鄰接矩陣：適用于稠密圖，存儲每對節(jié)點間的邊容量。

2.鄰接表：適用于稀疏圖，存儲每個節(jié)點的出邊信息（邊目標節(jié)點、容量、流量）。

（二）路徑搜索優(yōu)化

1.BFS：適用于尋找最短增廣路徑，適用于Dinic算法變種。

2.DFS：適用于Ford-Fulkerson算法，但效率較低。

（三）流量更新機制

1.可逆邊：使用反向邊記錄流量撤銷操作，提高效率（用于Edmonds-Karp算法）。

2.殘差網(wǎng)絡：構建殘差網(wǎng)絡表示剩余容量，簡化流量計算。

四、算法變種與優(yōu)化

（一）Ford-Fulkerson算法

1.基本實現(xiàn)：使用DFS搜索增廣路徑，時間復雜度O(VE^2)。

2.改進：通過阻塞流優(yōu)化搜索效率。

（二）Edmonds-Karp算法

1.基于BFS搜索：每次迭代保證最短路徑，時間復雜度O(V^2E)。

2.反向邊優(yōu)化：減少路徑搜索時間。

（三）Dinic算法

1.分層圖構建：通過BFS構建分層圖，DFS確定增廣路徑。

2.時間復雜度：O(V^2E)，適用于大規(guī)模網(wǎng)絡。

（四）Dinic算法的具體實現(xiàn)步驟

(1)構建分層圖：使用BFS從源點出發(fā)，構建可達節(jié)點的層級關系。

(2)構建增廣路徑：通過DFS在分層圖中尋找增廣路徑。

(3)迭代增廣：重復分層和路徑搜索，直至無增廣路徑。

五、應用示例

（一）網(wǎng)絡流量分配

1.輸入：節(jié)點5個，邊容量示例[3,2,4,2,3]，源點1，匯點5。

2.輸出：最大流量8，最小割集容量8（如邊1-2、2-5）。

（二）物流配送優(yōu)化

1.節(jié)點表示倉庫、配送點、客戶。

2.邊容量表示道路通行能力。

3.結果用于規(guī)劃最優(yōu)配送路徑。

六、總結

最大流最小割算法通過系統(tǒng)化的路徑搜索和流量調(diào)整，高效解決網(wǎng)絡流問題。實際應用中需根據(jù)網(wǎng)絡規(guī)模選擇合適變種（如Ford-Fulkerson、Edmonds-Karp、Dinic），并優(yōu)化數(shù)據(jù)結構以提高性能。通過分層圖和反向邊等技術，可顯著提升大規(guī)模網(wǎng)絡的計算效率。

一、概述

最大流最小割算法是圖論中解決網(wǎng)絡流問題的核心方法，用于在給定網(wǎng)絡中尋找從源點到匯點的最大流量，同時確定相應的最小割集。該算法基于Ford-Fulkerson方法及其變種，通過不斷尋找增廣路徑來迭代增加流量，直至無法再增廣為止。最小割則是將網(wǎng)絡分割為源點和匯點兩部分，且割集容量等于當前最大流量。本方案將詳細介紹該算法的實現(xiàn)步驟、關鍵數(shù)據(jù)結構和優(yōu)化策略，旨在提供一個清晰、可操作的實現(xiàn)框架。

二、算法實現(xiàn)步驟

最大流最小割算法的實現(xiàn)主要分為以下幾個步驟：

（一）初始化

1.創(chuàng)建網(wǎng)絡圖表示：選擇合適的圖數(shù)據(jù)結構來存儲網(wǎng)絡信息。常用的有鄰接矩陣和鄰接表。

鄰接矩陣適用于稠密圖，其中`graph[i][j]`表示節(jié)點`i`到節(jié)點`j`的容量，若無直接邊則記為0。

鄰接表適用于稀疏圖，對于每個節(jié)點`i`，存儲一個列表`(j,capacity,flow)`，表示從`i`出發(fā)的邊，`j`是目標節(jié)點，`capacity`是容量，`flow`是當前流量（初始為0）。

2.初始化流量：遍歷所有邊，將初始流量`flow`設為0。

3.設置源點和匯點：明確網(wǎng)絡中的起始節(jié)點`s`和結束節(jié)點`t`。

（二）增廣路徑搜索

1.選擇搜索方法：常用的搜索方法有深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）。

DFS：實現(xiàn)簡單，但可能找到非最優(yōu)路徑，導致Ford-Fulkerson算法效率低下。

BFS：能保證找到最短增廣路徑（邊數(shù)最少），適用于Edmonds-Karp算法。

2.實施路徑搜索：

從源點`s`開始，使用選定的搜索方法（如BFS）探索通往匯點`t`的路徑。

記錄路徑上的所有節(jié)點和邊。

路徑搜索應檢查每條邊`(u,v)`，確保其剩余容量`residual(u,v)=capacity(u,v)-flow(u,v)>0`。只有滿足此條件的邊才能被包含在增廣路徑中。

3.確定路徑上的瓶頸容量：在找到一條從`s`到`t`的有效增廣路徑后，計算該路徑上所有邊的最小剩余容量。這個最小值`bottleneck`就是本次迭代中可以增廣的最大流量。

（三）流量調(diào)整

1.沿增廣路徑增加流量：將路徑上每條邊的流量`flow(u,v)`增加`bottleneck`值。

`flow(u,v)=flow(u,v)+bottleneck`

2.更新剩余容量：同時更新每條邊的剩余容量。

`residual(u,v)=residual(u,v)-bottleneck`

對于反向邊`(v,u)`（用于表示反向流動或撤銷操作），更新其流量和剩余容量。

`flow(v,u)=flow(v,u)+bottleneck`

`residual(v,u)=residual(v,u)-bottleneck`

3.重復搜索與調(diào)整：返回步驟（二），繼續(xù)尋找新的增廣路徑并調(diào)整流量，直到無法找到任何增廣路徑為止。

（四）最小割確定

1.構建割集：當找不到增廣路徑時，當前網(wǎng)絡的最大流即為最大值`max_flow`。此時，存在一個將源點`s`和匯點`t`分割的割集`S`和`T`，其中`T`是從`s`可達的所有節(jié)點集合。

2.確定割集容量：割集`C(S,T)`是所有從`S`發(fā)向`T`的邊集合。割集的容量是這些邊原始容量`capacity(u,v)`的總和。

`cut_capacity=sum(capacity(u,v)forall(u,v)inC(S,T))`

3.判定最小割定理：根據(jù)最小割最大流定理，此時`max_flow=cut_capacity`。因此，找到的割集即為最小割。

三、關鍵數(shù)據(jù)結構

（一）網(wǎng)絡表示

1.鄰接矩陣：

優(yōu)點：查找邊信息快速（O(1)），實現(xiàn)簡單。

缺點：空間復雜度較高（O(V^2)），對于稀疏圖效率低。

適用場景：節(jié)點數(shù)量較少，邊密度較高。

示例存儲：`matrix[i][j]`存儲`i`到`j`的容量，`matrix[j][i]`存儲反向邊的容量（如果考慮反邊）。流量通過`flow[i][j]=matrix[i][j]-matrix[j][i]`間接計算或直接使用一個額外的`flow`矩陣。

2.鄰接表：

優(yōu)點：空間復雜度低（O(V+E)），對于稀疏圖效率高。

缺點：查找特定邊可能較慢（O(degree(i))）。

適用場景：節(jié)點數(shù)量多，邊數(shù)量相對較少。

示例存儲：`adj[i]`是一個列表，包含`(j,capacity,flow)`元組，表示從`i`出發(fā)的邊。

（二）路徑搜索優(yōu)化

1.BFS：用于尋找最短增廣路徑（邊的數(shù)量最少），是Edmonds-Karp算法的核心。BFS能保證在殘差網(wǎng)絡中找到最短增廣路徑，從而將Ford-Fulkerson的時間復雜度從O(VE^2)降低到O(V^2E)。

實現(xiàn)步驟：從源點`s`開始，初始化隊列和層級標記。隊列中存儲節(jié)點及其父節(jié)點（用于重建路徑）。逐層遍歷可達節(jié)點，直到匯點`t`被訪問或隊列為空。記錄從`s`到`t`的路徑。

2.DFS：Ford-Fulkerson算法原始實現(xiàn)中常用DFS搜索增廣路徑。DFS實現(xiàn)簡單，但每次找到的路徑不保證最短，可能導致增廣次數(shù)很多，效率低下（時間復雜度可達O(VE^2)）。在某些變種（如阻塞流優(yōu)化）中也可能使用DFS。

實現(xiàn)步驟：從源點`s`開始遞歸遍歷。若到達匯點`t`，則成功找到路徑。檢查路徑上每條邊的剩余容量。記錄路徑并計算瓶頸容量。

（三）流量更新機制

1.可逆邊（或反向邊）：在Ford-Fulkerson及其變種中，為了方便流量撤銷和殘差網(wǎng)絡管理，通常會為每條有向邊`(u,v)`增加一條容量為0的反向邊`(v,u)`。

增加流時：正向邊流量增加，反向邊流量減少。

撤銷流時：反向邊流量增加，正向邊流量減少。

剩余容量計算：`residual(u,v)=capacity(u,v)-flow(u,v)`，`residual(v,u)=flow(v,u)`。

2.殘差網(wǎng)絡：構建一個與原網(wǎng)絡結構相同的網(wǎng)絡，但邊的容量和流量基于剩余容量。正向邊的殘差容量是`capacity(u,v)-flow(u,v)`，反向邊的殘差容量是`flow(v,u)`。最大流問題轉(zhuǎn)化為在殘差網(wǎng)絡中找到從`s`到`t`的最大流。每次增廣都是基于殘差網(wǎng)絡進行的。

四、算法變種與優(yōu)化

（一）Ford-Fulkerson算法

1.基本實現(xiàn)：使用DFS搜索增廣路徑。時間復雜度分析：每次增廣路徑的查找時間與路徑長度成正比，增廣次數(shù)最多為`Vmax_flow`，因此總時間復雜度為O(VE^2)。適用于邊數(shù)較少的網(wǎng)絡。

2.改進：引入阻塞流（BlockingFlow）概念。在Ford-Fulkerson的DFS實現(xiàn)中，當搜索無法繼續(xù)前進時，可以嘗試回溯并修改之前的路徑選擇，以尋找更短的增廣路徑，而不是立即放棄。

（二）Edmonds-Karp算法

1.基于BFS搜索：這是Ford-Fulkerson算法的一個特定實現(xiàn)，其核心改進在于使用BFS而不是DFS來搜索增廣路徑。

2.時間復雜度：由于BFS總能找到最短增廣路徑（邊的數(shù)量最少），且增廣次數(shù)最多為`Vmax_flow`，每次BFS搜索的時間復雜度為O(E)，因此Edmonds-Karp算法的總時間復雜度為O(VE^2)。盡管與Ford-Fulkerson理論復雜度相同，但在實際中通常表現(xiàn)更好。

（三）Dinic算法

1.分層圖構建：Dinic算法的核心優(yōu)化在于引入了分層圖的概念。通過BFS從源點出發(fā)，構建一個分層圖，其中節(jié)點按層級劃分。只有當`u`在層級`l`，`v`在層級`l+1`時，邊`(u,v)`才可能在增廣路徑中。

2.構建增廣路徑：在分層圖中，使用DFS（稱為“管道DFS”）從匯點`t`開始反向搜索源點`s`，找到增廣路徑。由于分層圖的結構，管道DFS的效率很高。

3.時間復雜度：Dinic算法的分層圖構建復雜度為O(V^2)，管道DFS的復雜度為O(E)，每次迭代進行一次分層和一次管道DFS。因此，總時間復雜度為O(V^2E)，適用于大規(guī)模網(wǎng)絡。

（四）Dinic算法的具體實現(xiàn)步驟

(1)構建分層圖：初始化層級`level`數(shù)組。從源點`s`出發(fā)，使用BFS遍歷所有可達節(jié)點，并記錄每個節(jié)點的層級`level[v]=level[u]+1`。匯點`t`的層級即為分層圖的高度`h`。如果匯點`t`在分層圖中不可達，則最大流已達到`max_flow`，算法結束。

(2)構建增廣路徑：從匯點`t`開始，使用DFS（稱為“管道DFS”或Excess-FlowDFS”）在分層圖中搜索增廣路徑。

初始化一個“管道”數(shù)組`pipe`，記錄路徑上邊的方向和容量。

從`t`開始，嘗試沿邊`(u,v)`回溯到層級`level[u]-1`的節(jié)點。檢查邊`(u,v)`是否有效（即正向邊剩余容量`residual(u,v)>0`或反向邊`residual(v,u)>flow(v,u)`）。

若找到有效的邊，則將容量更新到`pipe`中，并繼續(xù)回溯。如果在層級0找到源點`s`，則一條增廣路徑被找到。

(3)執(zhí)行增廣：沿著管道`pipe`記錄的路徑，增加流量。計算路徑上的瓶頸容量`bottleneck`，更新正向邊流量和反向邊流量，并調(diào)整剩余容量。

(4)迭代：重復步驟（1）和（2），直到分層圖中匯點`t`不可達（即`level[t]==-1`）。此時，得到的`max_flow`即為網(wǎng)絡的最大流量。

五、應用示例

（一）網(wǎng)絡流量分配

1.場景描述：假設有一個物流配送網(wǎng)絡，包含倉庫（源點）、配送中心（中間節(jié)點）和零售店（匯點）。邊表示道路，容量表示道路的最大通行能力（車輛/小時）。

2.輸入示例：

節(jié)點：`s,a,b,t`(4個節(jié)點)

邊：

`s->a`:容量10

`s->b`:容量10

`a->b`:容量1

`a->t`:容量10

`b->t`:容量10

源點：`s`

匯點：`t`

3.運行算法：使用Edmonds-Karp算法（基于BFS）或Dinic算法。

4.輸出與解釋：

最大流量計算過程：

第一次增廣：路徑`s->a->t`，流量10。網(wǎng)絡狀態(tài)更新。

第二次增廣：路徑`s->b->t`，流量10。網(wǎng)絡狀態(tài)更新。

無法找到新的增廣路徑。

最大流量結果：20。

最小割集：將網(wǎng)絡分割為`S={s,a}`和`T={b,t}`的割集包括邊`a->t`和`b->t`，割集容量為`10+10=20`。符合最小割最大流定理。

（二）任務分配優(yōu)化

1.場景描述：多個工人（節(jié)點）需要處理多個任務（節(jié)點），每條邊表示工人能處理的任務及其處理能力（單位時間內(nèi)可完成工作量）。目標是最大化完成的總工作量。

2.輸入：節(jié)點代表工人和任務，邊代表工人處理任務的容量，源點代表所有工人集合，匯點代表所有任務集合。

3.輸出：最大可完成工作量，以及哪些工人分配給哪些任務以達成最大量。

4.應用：人力資源調(diào)度、項目任務分配等。

六、總結

最大流最小割算法通過系統(tǒng)化的路徑搜索和流量調(diào)整，高效解決網(wǎng)絡流問題。實際應用中需根據(jù)網(wǎng)絡規(guī)模選擇合適變種（如Ford-Fulkerson、Edmonds-Karp、Dinic），并優(yōu)化數(shù)據(jù)結構以提高性能。通過分層圖和反向邊等技術，可顯著提升大規(guī)模網(wǎng)絡的計算效率。理解并正確實現(xiàn)該算法，對于解決涉及資源分配、路徑規(guī)劃等優(yōu)化問題具有重要意義。

一、概述

最大流最小割算法是圖論中解決網(wǎng)絡流問題的核心方法，用于在給定網(wǎng)絡中尋找從源點到匯點的最大流量，同時確定相應的最小割集。該算法基于Ford-Fulkerson方法及其變種，通過不斷尋找增廣路徑來迭代增加流量，直至無法再增廣為止。最小割則是將網(wǎng)絡分割為源點和匯點兩部分，且割集容量等于當前最大流量。本方案將詳細介紹該算法的實現(xiàn)步驟、關鍵數(shù)據(jù)結構和優(yōu)化策略。

二、算法實現(xiàn)步驟

最大流最小割算法的實現(xiàn)主要分為以下幾個步驟：

（一）初始化

1.創(chuàng)建網(wǎng)絡圖表示：使用鄰接矩陣或鄰接表存儲邊的容量信息。

2.初始化流量：所有邊的初始流量為0。

3.設置源點和匯點：明確網(wǎng)絡中的起始節(jié)點和結束節(jié)點。

（二）增廣路徑搜索

1.使用深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜索（BFS）尋找從源點到匯點的可增廣路徑。

2.檢查路徑上每條邊的剩余容量，確保路徑有效（即每條邊流量未達到容量上限）。

3.記錄路徑上的最小剩余容量，作為本次增廣的流量調(diào)整值。

（三）流量調(diào)整

1.沿增廣路徑增加流量：將路徑上每條邊的流量增加最小剩余容量值。

2.更新網(wǎng)絡圖：調(diào)整邊的流量，并計算剩余容量（容量-流量）。

3.重復搜索：直至無法找到新的增廣路徑。

（四）最小割確定

1.構建最小割集：通過網(wǎng)絡割分，找到割集容量等于最大流量的分割方式。

2.計算割集容量：匯總割集邊上的原始容量，作為最小割值。

三、關鍵數(shù)據(jù)結構

（一）網(wǎng)絡表示

1.鄰接矩陣：適用于稠密圖，存儲每對節(jié)點間的邊容量。

2.鄰接表：適用于稀疏圖，存儲每個節(jié)點的出邊信息（邊目標節(jié)點、容量、流量）。

（二）路徑搜索優(yōu)化

1.BFS：適用于尋找最短增廣路徑，適用于Dinic算法變種。

2.DFS：適用于Ford-Fulkerson算法，但效率較低。

（三）流量更新機制

1.可逆邊：使用反向邊記錄流量撤銷操作，提高效率（用于Edmonds-Karp算法）。

2.殘差網(wǎng)絡：構建殘差網(wǎng)絡表示剩余容量，簡化流量計算。

四、算法變種與優(yōu)化

（一）Ford-Fulkerson算法

1.基本實現(xiàn)：使用DFS搜索增廣路徑，時間復雜度O(VE^2)。

2.改進：通過阻塞流優(yōu)化搜索效率。

（二）Edmonds-Karp算法

1.基于BFS搜索：每次迭代保證最短路徑，時間復雜度O(V^2E)。

2.反向邊優(yōu)化：減少路徑搜索時間。

（三）Dinic算法

1.分層圖構建：通過BFS構建分層圖，DFS確定增廣路徑。

2.時間復雜度：O(V^2E)，適用于大規(guī)模網(wǎng)絡。

（四）Dinic算法的具體實現(xiàn)步驟

(1)構建分層圖：使用BFS從源點出發(fā)，構建可達節(jié)點的層級關系。

(2)構建增廣路徑：通過DFS在分層圖中尋找增廣路徑。

(3)迭代增廣：重復分層和路徑搜索，直至無增廣路徑。

五、應用示例

（一）網(wǎng)絡流量分配

1.輸入：節(jié)點5個，邊容量示例[3,2,4,2,3]，源點1，匯點5。

2.輸出：最大流量8，最小割集容量8（如邊1-2、2-5）。

（二）物流配送優(yōu)化

1.節(jié)點表示倉庫、配送點、客戶。

2.邊容量表示道路通行能力。

3.結果用于規(guī)劃最優(yōu)配送路徑。

六、總結

最大流最小割算法通過系統(tǒng)化的路徑搜索和流量調(diào)整，高效解決網(wǎng)絡流問題。實際應用中需根據(jù)網(wǎng)絡規(guī)模選擇合適變種（如Ford-Fulkerson、Edmonds-Karp、Dinic），并優(yōu)化數(shù)據(jù)結構以提高性能。通過分層圖和反向邊等技術，可顯著提升大規(guī)模網(wǎng)絡的計算效率。

一、概述

最大流最小割算法是圖論中解決網(wǎng)絡流問題的核心方法，用于在給定網(wǎng)絡中尋找從源點到匯點的最大流量，同時確定相應的最小割集。該算法基于Ford-Fulkerson方法及其變種，通過不斷尋找增廣路徑來迭代增加流量，直至無法再增廣為止。最小割則是將網(wǎng)絡分割為源點和匯點兩部分，且割集容量等于當前最大流量。本方案將詳細介紹該算法的實現(xiàn)步驟、關鍵數(shù)據(jù)結構和優(yōu)化策略，旨在提供一個清晰、可操作的實現(xiàn)框架。

二、算法實現(xiàn)步驟

最大流最小割算法的實現(xiàn)主要分為以下幾個步驟：

（一）初始化

1.創(chuàng)建網(wǎng)絡圖表示：選擇合適的圖數(shù)據(jù)結構來存儲網(wǎng)絡信息。常用的有鄰接矩陣和鄰接表。

鄰接矩陣適用于稠密圖，其中`graph[i][j]`表示節(jié)點`i`到節(jié)點`j`的容量，若無直接邊則記為0。

鄰接表適用于稀疏圖，對于每個節(jié)點`i`，存儲一個列表`(j,capacity,flow)`，表示從`i`出發(fā)的邊，`j`是目標節(jié)點，`capacity`是容量，`flow`是當前流量（初始為0）。

2.初始化流量：遍歷所有邊，將初始流量`flow`設為0。

3.設置源點和匯點：明確網(wǎng)絡中的起始節(jié)點`s`和結束節(jié)點`t`。

（二）增廣路徑搜索

1.選擇搜索方法：常用的搜索方法有深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）。

DFS：實現(xiàn)簡單，但可能找到非最優(yōu)路徑，導致Ford-Fulkerson算法效率低下。

BFS：能保證找到最短增廣路徑（邊數(shù)最少），適用于Edmonds-Karp算法。

2.實施路徑搜索：

從源點`s`開始，使用選定的搜索方法（如BFS）探索通往匯點`t`的路徑。

記錄路徑上的所有節(jié)點和邊。

路徑搜索應檢查每條邊`(u,v)`，確保其剩余容量`residual(u,v)=capacity(u,v)-flow(u,v)>0`。只有滿足此條件的邊才能被包含在增廣路徑中。

3.確定路徑上的瓶頸容量：在找到一條從`s`到`t`的有效增廣路徑后，計算該路徑上所有邊的最小剩余容量。這個最小值`bottleneck`就是本次迭代中可以增廣的最大流量。

（三）流量調(diào)整

1.沿增廣路徑增加流量：將路徑上每條邊的流量`flow(u,v)`增加`bottleneck`值。

`flow(u,v)=flow(u,v)+bottleneck`

2.更新剩余容量：同時更新每條邊的剩余容量。

`residual(u,v)=residual(u,v)-bottleneck`

對于反向邊`(v,u)`（用于表示反向流動或撤銷操作），更新其流量和剩余容量。

`flow(v,u)=flow(v,u)+bottleneck`

`residual(v,u)=residual(v,u)-bottleneck`

3.重復搜索與調(diào)整：返回步驟（二），繼續(xù)尋找新的增廣路徑并調(diào)整流量，直到無法找到任何增廣路徑為止。

（四）最小割確定

1.構建割集：當找不到增廣路徑時，當前網(wǎng)絡的最大流即為最大值`max_flow`。此時，存在一個將源點`s`和匯點`t`分割的割集`S`和`T`，其中`T`是從`s`可達的所有節(jié)點集合。

2.確定割集容量：割集`C(S,T)`是所有從`S`發(fā)向`T`的邊集合。割集的容量是這些邊原始容量`capacity(u,v)`的總和。

`cut_capacity=sum(capacity(u,v)forall(u,v)inC(S,T))`

3.判定最小割定理：根據(jù)最小割最大流定理，此時`max_flow=cut_capacity`。因此，找到的割集即為最小割。

三、關鍵數(shù)據(jù)結構

（一）網(wǎng)絡表示

1.鄰接矩陣：

優(yōu)點：查找邊信息快速（O(1)），實現(xiàn)簡單。

缺點：空間復雜度較高（O(V^2)），對于稀疏圖效率低。

適用場景：節(jié)點數(shù)量較少，邊密度較高。

示例存儲：`matrix[i][j]`存儲`i`到`j`的容量，`matrix[j][i]`存儲反向邊的容量（如果考慮反邊）。流量通過`flow[i][j]=matrix[i][j]-matrix[j][i]`間接計算或直接使用一個額外的`flow`矩陣。

2.鄰接表：

優(yōu)點：空間復雜度低（O(V+E)），對于稀疏圖效率高。

缺點：查找特定邊可能較慢（O(degree(i))）。

適用場景：節(jié)點數(shù)量多，邊數(shù)量相對較少。

示例存儲：`adj[i]`是一個列表，包含`(j,capacity,flow)`元組，表示從`i`出發(fā)的邊。

（二）路徑搜索優(yōu)化

1.BFS：用于尋找最短增廣路徑（邊的數(shù)量最少），是Edmonds-Karp算法的核心。BFS能保證在殘差網(wǎng)絡中找到最短增廣路徑，從而將Ford-Fulkerson的時間復雜度從O(VE^2)降低到O(V^2E)。

實現(xiàn)步驟：從源點`s`開始，初始化隊列和層級標記。隊列中存儲節(jié)點及其父節(jié)點（用于重建路徑）。逐層遍歷可達節(jié)點，直到匯點`t`被訪問或隊列為空。記錄從`s`到`t`的路徑。

2.DFS：Ford-Fulkerson算法原始實現(xiàn)中常用DFS搜索增廣路徑。DFS實現(xiàn)簡單，但每次找到的路徑不保證最短，可能導致增廣次數(shù)很多，效率低下（時間復雜度可達O(VE^2)）。在某些變種（如阻塞流優(yōu)化）中也可能使用DFS。

實現(xiàn)步驟：從源點`s`開始遞歸遍歷。若到達匯點`t`，則成功找到路徑。檢查路徑上每條邊的剩余容量。記錄路徑并計算瓶頸容量。

（三）流量更新機制

1.可逆邊（或反向邊）：在Ford-Fulkerson及其變種中，為了方便流量撤銷和殘差網(wǎng)絡管理，通常會為每條有向邊`(u,v)`增加一條容量為0的反向邊`(v,u)`。

增加流時：正向邊流量增加，反向邊流量減少。

撤銷流時：反向邊流量增加，正向邊流量減少。

剩余容量計算：`residual(u,v)=capacity(u,v)-flow(u,v)`，`residual(v,u)=flow(v,u)`。

2.殘差網(wǎng)絡：構建一個與原網(wǎng)絡結構相同的網(wǎng)絡，但邊的容量和流量基于剩余容量。正向邊的殘差容量是`capacity(u,v)-flow(u,v)`，反向邊的殘差容量是`flow(v,u)`。最大流問題轉(zhuǎn)化為在殘差網(wǎng)絡中找到從`s`到`t`的最大流。每次增廣都是基于殘差網(wǎng)絡進行的。

四、算法變種與優(yōu)化

（一）Ford-Fulkerson算法

1.基本實現(xiàn)：使用DFS搜索增廣路徑。時間復雜度分析：每次增廣路徑的查找時間與路徑長度成正比，增廣次數(shù)最多為`Vmax_flow`，因此總時間復雜度為O(VE^2)。適用于邊數(shù)較少的網(wǎng)絡。

2.改進：引入阻塞流（BlockingFlow）概念。在Ford-Fulkerson的DFS實現(xiàn)中，當搜索無法繼續(xù)前進時，可以嘗試回溯并修改之前的路徑選擇，以尋找更短的增廣路徑，而不是立即放棄。

（二）Edmonds-Karp算法

1.基于BFS搜索：這是Ford-Fulkerson算法的一個特定實現(xiàn)，其核心改進在于使用BFS而不是DFS來搜索增廣路徑。

2.時間復雜度：由于BFS總能找到最短增廣路徑（邊的數(shù)量最少），且增廣次數(shù)最多為`Vmax_flow`，每次BFS搜索的時間復雜度為O(E)，因此Edmonds-Karp算法的總時間復雜度為O(VE^2)。盡管與Ford-Fulkerson理論復雜度相同，但在實際中通常表現(xiàn)更好。

（三）Dinic算法

1.分層圖構建：Dinic算法的核心優(yōu)化在于引入了分層圖的概念。通過BFS從源點出發(fā)，構建一個分層圖，其中節(jié)點按層級劃分。只有當`u`在層級`l`，`v`在層級`l+1`時，邊`(u,v)`才可能在增廣路徑中。

2.構建增廣路徑：在分層圖中，使用DFS（稱為“管道DFS”）從匯點`t`開始反向搜索源點`s`，找到增廣路徑。由于分層圖的結構，管道DFS的效率很高。

3.時間復雜度：Dinic算法的分層圖構建復雜度為O(V^2)，管道DFS的復雜度為O(E)，每次迭代進行一次分層和一次管道DFS。因此，總時間復雜度為O(V^2E)，適用于大規(guī)模網(wǎng)絡。

（四）Dinic算法的具體實現(xiàn)步驟

(1)構建分層圖：初始化層級`level`數(shù)組。從源點`s`出發(fā)，使用BFS遍歷所有可達節(jié)點，并記錄每個節(jié)點的層級`level[v]=level[u]+1`。匯點`t`的層級即為分層圖的高度`h`。如果匯點`t`在分層圖中不可達，則最大流已達到`max_flow`，算法結束。

(2)構建增廣路徑：從匯點`t`開始，使用DFS（稱為“管