Blossom 演算法

Blossom 演算法（Edmonds 1965）在一個（可能帶權重的）圖中找到一個最大獨立邊集。雖然對於二分圖，使用匈牙利最大匹配演算法可以相當容易地找到最大獨立邊集，但一般情況更為困難。Edmonds 的 Blossom 演算法從一個極大獨立邊集開始，嘗試將其擴充套件為最大獨立邊集，利用的性質是匹配是最大匹配當且僅當該匹配不容許增廣路徑。

Blossom 演算法透過樹搜尋來檢查增廣路徑的存在性，這與二分圖的情況類似，但對一般情況下可能出現的奇數長度環進行了特殊處理。這種環被稱為花（blossom）。花可以被收縮，並遞迴地重新開始搜尋。如果在收縮後的圖中找到增廣路徑，它可以被擴充套件透過花，從而得到原始圖中的增廣路徑；該交錯路徑可以用來將匹配增加一條邊。如果遞迴過程遇到沒有增廣路徑的狀態，那麼原始圖中也沒有。