匈牙利最大匹配演算法

匈牙利演算法在一個圖上找到一個最大獨立邊集。該演算法從任意匹配 開始，並透過廣度優先搜尋構建一棵樹，以找到一條增廣路徑，即一條路徑 ，它起始和終止於未匹配的頂點，其第一條和最後一條邊不在 中，並且其邊在 的外部和內部交替。如果搜尋成功，則 和 中邊的對稱差產生一個比 多一條邊的匹配。新增該邊，然後執行另一次搜尋以查詢新的增廣路徑。如果搜尋不成功，則演算法終止，並且 必須是最大尺寸的匹配。

作為額外的獎勵，樹資料提供了一個頂點覆蓋。

如果樹搜尋不成功（就像在最後一樣），那麼頂點覆蓋的大小與匹配的大小相同，這證明了最終匹配具有最大可能的尺寸。