二分圖最大匹配km算法

Kuhn-Munkres (KM) 算法，也稱為匈牙利算法，是用來解決二分圖最大匹配問題的一種有效算法。二分圖是一種特殊的圖，它的頂點可以分為兩個不相交的集合，並且每個邊都連接著一個集合中的頂點與另一個集合中的頂點。

二分圖最大匹配問題的目標是在二分圖中找到一組邊，使得每個頂點最多只與一條邊匹配，並且匹配的邊數盡可能多。KM算法可以找到這樣的一組最大匹配邊。

KM算法的基本思想是通過不斷地減少圖中的剩餘頂點數量來找到最大匹配。算法的步驟如下：

1. 初始化：將圖中的所有頂點都視為剩餘頂點。

2. 貪心匹配：選擇一個剩餘頂點，並找到與其匹配的邊，如果有多條邊可以匹配，則選擇權重最小的邊。

3. 移除匹配的頂點：將匹配的頂點及其匹配的頂點從圖中移除，並將與該頂點相連的邊的對應端點也從圖中移除。

4. 更新剩餘頂點：將與剛才移除的邊相連的剩餘頂點標記為已匹配，並更新其權重。

5. 重複：如果圖中還有剩餘頂點，則返回步驟2，否則算法結束。

KM算法的時間複雜度為 O(n^3)，其中 n 是圖中頂點的數量。雖然這個時間複雜度看起來很高，但是在實際應用中，KM算法通常能夠在幾十個循環內找到最大匹配，因此實際運行時間通常比時間複雜度所預期的要短。

需要注意的是，KM算法並不僅僅用於解決二分圖最大匹配問題，它也可以用於解決更一般的線性規劃問題。在這些問題中，KM算法可以用來找到一個滿足所有限制條件的最優解。