基于標號法求解最大流問題的算法研究

于曉倩 陳燕 李龍霞

（大連海事大學航運經濟與管理學院 遼寧省大連市 116026）

1 序言

結構化程序設計的先驅Niklaus Wirth曾提出：程序=數據結構+算法。實際問題通過獲得相應的計算機外部邏輯表示，轉化為計算機內部存儲結構，輔以算法，即可得到解決。現實中許多系統都存在著各種各樣的流，如公路系統中有車輛流，水利系統中有水流，電力系統中有電流，等等。各種流匯集成連通網絡，網絡中每條邊的最大通過能力是有限的，實際流量不能超過其容量。基于這一前提，可以解決許多實際工程類問題。

最大流問題以圖論的知識為理論基礎，應用極為廣泛，20世紀50年代福特(Ford)、富克遜(Fulkerson)建立的“網絡流理論”，是網絡應用的重要組成部分。基本的最大流問題就是通過充分利用裝置的能力使得運輸的流量最大。目前這一問題已經有許多算法可以解決，如EK算法、SAP算法、DINIC算法、HLPP算法等。本文是從管理運籌學中的福特-富爾克遜標號法提煉出算法，利用數據結構中的圖結構自主解決最大流問題。

2 問題背景與分析

為解決山區水資源運輸問題，現從出發地途經各村莊，使得水資源運送至目的地時水流量最大。根據數據結構思想建模，可以將各村莊抽象為頂點，根據流的流向以及運輸路徑，可以將流抽象為帶權重的弧其中r為容量，x為當前流量，構成有向網。那么最大流問題就可以利用圖論知識來解決。圖是一種數據結構，加上一組基本操作，就構成了抽象數據類型：

圖的物理結構比較復雜。由于無法以數據元素在存儲區中的物理位置來表示元素之間的聯系，所以圖沒有順序存儲結構，但可以借助二維數組來表示（如鄰接矩陣），以及鏈式存儲（如鄰接表等）來進行存儲。具體可參考嚴蔚敏版《數據結構》第六章。

3 案例分析與實現

3.1 案例描述

某山區水源不足，現欲將水流從臨河村莊A運輸至村莊F，途經村莊B、C、D、E。部分村子之間鋪設有管道，管道的運輸能力（即容量）不同。各村之間的實際管道情況如圖1所示，試求從A村運輸到F村的最大水流量。

圖1：村莊間管道詳情

3.2 案例分析

觀察易知，該問題屬于圖的應用，邏輯結構為圖。由于圖有向且邊也存儲了相關信息，確定為有向網，可使用鄰接矩陣或鄰接表來存儲。

鄰接矩陣與鄰接表各有使用環境與優缺點。如鄰接矩陣適用于稠密圖且便于判斷兩頂點間是否有邊，但空間復雜度高等；鄰接表則適用于稀疏圖且空間效率高，但不便于確定兩點間是否有邊等。計算可得上圖邊數，為稀疏圖，暫選用鄰接表進行存儲。

分析整個標號法，就是從始點v0出發，標記后壓入標記棧并將所得信息壓入中間棧；若標記棧不空，則彈出頂點并尋找其鄰接點判斷是否被標記；若未被標記，則按公式（1）求得兩點間弧的最大調整量b(vj)（尋找鄰接點時只判斷是否鄰接，并不確定弧的方向，因此弧的方向不同，b(vj)的計算方式不同），并將信息壓入棧。

所有頂點判斷完畢后，讀取中間棧頂信息，若終點vt也被標記，則記調整量θ=b(vt)；不斷彈出中間棧信息，從vt開始，不斷回溯至第一個標號，就能得到一條由標號點和相應弧連接而成的、從v0到vt的增廣鏈μ。對增廣鏈上各弧的流量按公式（2）進行調整；調整后從始點重新開始，直至找不到增廣鏈（即終點vt未被標記），此時根據始點的流出量或終點的匯集量求和即得最大流量值。

基于以上分析，需要一個標記棧來確定頂點標號的順序；一個visited數組來標志該頂點是否已經被標號；一個中間棧來保存頂點的標號信息。標記棧只需存儲頂點數據即可。因為增廣鏈是從vt回溯到第一個標號點v0，因此中間棧需保存的信息應包括前一點vi、當前標記點vj以及該邊(vi, vj)上的最大可調整量b(vj)；根據公式（1），b(vj)的獲得需要與b(vi)進行比較，因為棧只能讀取棧頂元素，無法做到隨機存取，因此還需定義一個flag數組來隨機存取每個頂點的b值。此過程需判斷關聯弧是否存在，鄰接矩陣比鄰接表更容易實現查找確認，因此最終圖的存儲結構確定為鄰接矩陣：其中，r為總容量，x為當前流量

圖2：算法流程圖

3.3 算法步驟與流程圖

（1）從始點v0出發，將始點壓入標記棧，始點的初始信息壓入中間棧，置visited[v]的值為TRUE，flag[v]值為∞。

（2）只要標記棧不空，則重復下述操作：

1.彈出標記棧頂元素v；

2.一次將v的所有鄰接點w壓入鄰接點棧；

3.只要鄰接點棧不空；

4.彈出鄰接點棧頂元素w，如果visited[w]的值為FALSE，且能求得頂點w的新信息(start,end,value)，則將w壓入標記棧，將新信息壓入中間棧；置visited[w]的值為TRUE，flag[v]值為value；

（3）標記棧為空時，判斷終點是否被標記，如果visited[G.vexnum-1]值為TRUE，則尋得增廣鏈并改變增廣鏈上弧的流量，從(1)重新開始。

（4）如果visited[G.vexnum-1]值為FALSE，即可根據始點的流出量或終點的匯集量得最大流量。

圖2中(1)-(4)與算法步驟相對應。

3.4 算法實現過程

3.4.1 初始條件

對圖3左圖求最大流，弧權值如(9,7)，9為容量，7為當前流量。其鄰接矩陣如圖3右圖所示。

3.4.2 操作過程

（1）首先進行初始化數組：visited[]來標識頂點是否被標記；flag[]來保存相應弧上的最大可調整量。如圖4所示。

圖3：有向網及其鄰接矩陣存儲

圖4：初始化數組

圖5：第一次嘗試標記頂點

圖6：第一次調整增廣鏈

圖7：程序運行結果

（2）第一次嘗試標記頂點，最終結果如圖5所示。

此時循環尚未結束，但visited數組已全為1，說明頂點已全部標記，剩余只有彈出棧操作，直至標記棧a為空。a棧空后，判斷是否visited[5]=1，若為1，則說明終點被標記，存在增廣鏈，進入調整增廣鏈過程。

（3）第一次調整增廣鏈，如圖6所示。

3.2.3 程序運行結果

如圖7所示。

4 總結與展望

通過對數據結構課程的學習，結合管理運籌學科知識，完成了這次獨立自主解決實際問題的嘗試。通過嘗試，理清了解決問題的基本步驟：按照問題描述，建立相應模型，確定計算機外部的邏輯結構，根據實際需求轉化為計算機內部存儲結構，編寫算法形成程序，最終解決問題；對數據結構有了更深層次的理解，為之后的學習打下了一定的基礎。

確定計算機外部邏輯結構時，要抓住本質，進行合理地抽象。本文案例相對明顯，可以容易地確定為圖結構。實際問題大多數要抽象得多，如工作分配問題等。確定邏輯結構后選定內部存儲結構時，要充分考慮各種情況，不同的存儲結構有各自的優點和適用情況。例如本文中圖選用鄰接矩陣或者鄰接表存儲都可以，但考慮到算法中需要多次確定兩頂點間是否存在有向弧，這時鄰接矩陣就要比鄰接表要方便得多。在解決問題的基礎上，一個優秀的算法還需要考慮時間復雜度和空間復雜度，進而對算法不斷進行優化，本文算法還有很大的改進空間，仍需進一步思考嘗試。