如果G為加權二分圖,則權值和最大的完備匹配稱為最佳匹配.求一個二分圖的最佳匹配的普遍算法是KM(Kuhn-Munkres)算法.KM算法的基本思想是,把權值轉化為可行頂標,再用匈牙利算法求出一組完備匹配,如果無法求出完備匹配,則修改可行頂標,直至找到完備匹配為止,這時的完備匹配為最佳匹配.Kuhn－Munkras算法流程：(1)初始化可行頂標的值(2)用匈牙利算法尋找完備匹配(3)若未找到完備匹配則修改可行頂標的值(4)重複(2)(3)直到找到相等子圖的完備匹配為止
