本文始發于個人公衆号：TechFlow，原創不易，求個關注
今天是算法與資料結構專題的第31篇文章，我們一起來聊聊二分圖比對與匈牙利算法。
在上一篇文章當中我們介紹了一個有趣的穩定婚姻問題，模拟了男男女女配對的婚戀場景，并且研究了一下讓比對更加穩定的Gale-Shapley算法。如果錯過了這篇文章的同學可以從下方的傳送門回顧一下婚姻穩定問題的具體内容。
學算法還能指導找對象？是的，這就是大名鼎鼎的穩定婚姻算法
在上一篇文章的末尾我們曾經提到過，婚姻比對問題本質上來說其實是二分圖比對的問題。那麼什麼又是二分圖比對呢？二分圖比對的問題又該通過什麼算法來解決呢？下面就讓我們一起從最基礎的概念開始。
二分圖比對
二分圖的概念很簡單，就是在一個無向圖當中，所有的點可以分成兩個子集。這兩個子集當中的點各自互不相交，并且圖當中的所有邊關聯的頂點都屬于兩個不同的集合。單純用語言描述有一點吃力，其實我們找一張圖看一下就明白了。
在上圖當中很明顯左邊的豎着的三個點是一個集合，右邊豎着的三個點是另外一個集合。兩個集合之間有邊相連，集合内部互不連通。
比對與最大比對
在二分圖當中，如果我們選擇了一條邊就會連通對應的兩個點。這也就構成了一個比對，我們規定一個頂點最多隻能構成一個比對，也就是說所有的比對之間沒有公共的點。
對于一張二分圖而言，構成的比對數量可以是不同的，其中比對數量最多的情況叫做最大比對。如果所有頂點都有了比對，那麼就稱這種情況為完美比對。
今天要介紹的匈牙利算法就是一種用來完成二分圖最大比對的算法。
匈牙利算法
匈牙利我們都知道是一個國家的名字，這和算法的發明人有關。匈牙利算法的發明人Edmonds在1965年提出了匈牙利算法，我也不知道為什麼算法發明人是匈牙利的就叫匈牙利算法，也沒見過其他以國家命名的算法，是因為匈牙利人提出的算法太少了嗎？
匈牙利算法的核心原理非常簡單，就是尋找增廣路徑，進而達成最大比對。
我們用通俗易懂的語言來解釋一下算法的含義，我們還用上面那張圖作為舉例。我們首先将左邊的1和右側的a，左邊的2和右側的b節點比對。
這樣當我們想要比對左側的3号節點的時候發現了一個問題，那就是能夠和3号節點構成比對的a和b節點都已經被占據了。是以3号節點無法構成比對，但是我們觀察一下圖就能發現，如果1和2号節點稍微調整一下比對的情況，其實是可以給3号節點挪出一個位置來的。
具體怎麼操作呢？
我們周遊3号節點能夠比對的節點，首先找到a節點，發現a節點已經被占用了。于是我們找到a節點比對的節點也就是1号節點，試着讓它重新找一個比對，給3号節點挪出位置來。于是我們遞歸安排1号節點，我們周遊到b節點，發現b節點也被占用了。于是我們同樣遞歸與b節點比對的2号節點，看看2号節點能不能找到新的坑騰出一個位置來。
我們觀察一下發現2号節點可以和c節點構成比對，騰出位置來給1号，這樣1号就能騰出位置來給3号節點了。是以最終的比對結果就成了這樣：
其中藍線是調整比對之前的結果，紅色是調整之後的結果。
本質上來說，匈牙利算法就是一個調整比對的過程。通過遞歸調用的形式去嘗試調整已經占據了發生沖突位置的比對，騰出位置來給右面的節點。
我們把匈牙利算法的原理和Gale-Shapley算法比較一下，有沒有發現什麼？其實這兩個算法的核心原理是一樣的，在GS算法當中我們是先由男生發起追求，盡可能構成比對。然後單身的男生再一輪一輪發起表白，如果有更好的比對則斷開之前的比對。在穩定婚姻問題當中我們定義了比對的好壞，而在原生的二分圖比對的問題當中比對是不分好壞的。如果我們抛開比對好壞不談，把優質男生搶占劣質男生女朋友的過程看成是比對調整的過程，那麼其實這兩個算法的核心幾乎是一樣的。
唯一不同的是GS算法是一輪一輪的疊代，直到所有節點完成比對為止。因為在婚姻比對問題當中是一定有完美比對的解的，而二分圖比對的問題當中，完美比對的情況可能不一定存在。是以我們不能使用這樣疊代的方式進行，而使用遞歸進行更好一些。換句話來說匈牙利算法研究的是二分圖比對的通解，而GS算法隻是二分圖算法的一個特殊案例。
代碼實作
匈牙利算法的思路如果學會了，代碼其實非常簡單，就是一個簡單的遞歸調用。
def find_match(x):
for i in range(n):
if graph[x][i] and not tried[i]:
tried[i] = True
if match[i] == -1 or find_match(match[i]):
match[i] = x
return True
return False
for i in range(n):
tried = [0 for _ in range(n)]
find_match(i)
我們再試着用匈牙利算法來做一下婚姻穩定問題，因為在婚姻穩定問題當中每兩個異性之間都有配對的可能，是以不需要再判斷連通的情況了。并且構成的比對有品質好壞的差别，是以需要去掉是否嘗試過的判斷。
girls_matched = [-1 for _ in range(n)]
boys_round = [0 for _ in range(n)]
boys_matched = [-1 for _ in range(n)]
def find_match(x):
for i in range(n):
idx = girls[i].index(x)
mate = girls_matched[i]
mate_id = n+1 if mate == -1 else girls[i].index(mate)
# 如果女孩i沒有對象或者是對象比x男生弱
if mate == -1 or (idx < mate_id and find_match(girls_matched[i])):
girls_matched[i] = x
boys_matched[x] = i
return True
return False
for i in range(n):
# 對i男生進行比對
find_match(i)
我們運作一下這段代碼：
結果當然是正确的，但是如果我們嘗試用GS算法示範一下會發現這兩個算法的結果不一樣。這是為什麼呢？原因也很簡單，因為GS算法男生追求的順序是自己喜好的順序，而匈牙利算法當中是按照編号順序，是以是以得到的結果不同。
總結
關于匈牙利算法的原理與介紹就到這裡結束了，對于二分圖比對問題來說我們有很多種算法可以解決，但是匈牙利算法是其中比較簡單易于了解與實作的一種。如果我們将它與之前介紹的GS算法相對比，可以發現很多共性和連通的部分。文中隻是簡單介紹了一些，如果仔細研究下去還會發現很多有趣的點。
今天的文章到這裡就結束了，如果喜歡本文的話，請來一波素質三連，給我一點支援吧（關注、轉發、點贊）。
- END -