匈牙利算法

匈牙利算法

求最大匹配的一種顯而易見的算法是:先找出全部匹配，然後保留匹配數最多的。但是這個算法的複雜度為邊數的指數級函數。因此，需要尋求一種更加高效的算法。

增廣路的定義(也稱增廣軌或交錯軌)：

若P是圖G中一條連通兩個未匹配頂點的路徑，并且屬于M的邊和不屬于M的邊（即已匹配和待匹配的邊）在P上交替出現，則稱P為相對于M的一條增廣路徑。

結論

由增廣路的定義可以推出下述三個結論：

1－P的路徑長度必定為奇數，第一條邊和最後一條邊都不屬于M。

2－P經過取反操作可以得到一個更大的匹配M’。

3－M為G的最大匹配當且僅當不存在相對于M的增廣路徑。

用增廣路求最大匹配（稱作匈牙利算法，匈牙利數學家Edmonds于1965年提出）

算法輪廓：

(1)置M為空

(2)找出一條增廣路徑P，通過取反操作獲得更大的匹配M’代替M

(3)重複(2)操作直到找不出增廣路徑為止