匈牙利算法——最大匹配问题详解
? 2017年中興提前批校招，就考了一題匈牙利算法。
? 匈牙利算法是由匈牙利數學家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性證明的思想，它是部圖匹配最常見的算法，該算法的核心就是尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的算法。
? 先了解一些概念性的東西吧。
?1.二分圖
? 設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關聯的兩個頂點i和j分別屬于這兩個不同的頂點集(i in A,j in B)，則稱圖G為一個二分圖。一個二分圖的例子：
? ? ? ? ? ? ? ? ? ? ? ?
? 2.最大匹配&完美匹配
? 在圖論中，一個“匹配”（matching）是一個邊的集合，其中任意兩條邊都沒有公共頂點。
? 最大匹配：一個圖所有匹配中，所含匹配邊數最多的匹配，稱為這個圖的最大匹配。
? 完美匹配：如果一個圖的某個匹配中，所有的頂點都是匹配點，那么它就是一個完美匹配。
? 3.交替路&增廣路
? 交替路：從一個未匹配點出發，依次經過非匹配邊、匹配邊、非匹配邊...形成的路徑叫交替路。
? 增廣路：從一個未匹配點出發，走交替路，如果途徑另一個未匹配點（出發的點不算），則這條交替路稱為增廣路。
? 注意：把增廣路徑上的所有第奇數條邊加入到原匹配中去，并把增廣路徑中的所有第偶數條邊從原匹配中刪除（這個操作稱為增廣路徑的取反），則新的匹配數就比原匹配數增加了1個。
? 4.思想與算法
? 思想：看這么一個例子，把左邊1，2，3，4和右邊a,b,c,d來進行匹配
? ? ? ? ? ? ? ? ? ? ?
? 一開始我們給1分配a,1和a之間連上紅線表示建立匹配。
? ? ? ? ? ? ? ? ? ? ?
? 然后接著給2分配b,2和b連上紅線表示匹配。
? ? ? ? ? ? ? ? ? ? ? ?
? 緊接著給3分配，這時候發現a,b已經都有所屬了，我們嘗試給1重新分配，把原來的分配拆掉，用藍線表示。
? ? ? ? ? ? ? ? ? ? ? ?
? 但是很快我們發現1重新分配不了，b已經有所屬，那么繼續嘗試給2重新分配，把原來的分配拆掉，用藍線表示。2重新分配到c,用紅線表示。
? ? ? ? ? ? ? ? ? ? ? ?
? 這個時候，1可以重新分配到b,用紅線表示。
? ? ? ? ? ? ? ? ? ? ? ?
? 最后，3就可以分配到a,用紅線表示。
? ? ? ? ? ? ? ? ? ? ? ? ?
? 對于4，由于c已經被分配，而且嘗試給其他1，2，3重新分配無法實現，就此結束。基本原則就是在原有匹配基礎上重新分配，看是否可以添加一個新的匹配。
? 下面，以一個相親的例子來具體說明一下（這個例子轉載于http://blog.csdn.net/dark_scope/article/details/8880547）
? 通過數代人的努力，你終于趕上了剩男剩女的大潮，假設你是一位光榮的新世紀媒人，在你的手上有N個剩男，M個剩女，每個人都可能對多名異性有好感（-_-||暫時不考慮特殊的性取向），如果一對男女互有好感，那么你就可以把這一對撮合在一起，現在讓我們無視掉所有的單相思（好憂傷的感覺），你擁有的大概就是下面這樣一張關系圖，每一條連線都表示互有好感。
? 本著救人一命，勝造七級浮屠的原則，你想要盡可能地撮合更多的情侶，匈牙利算法的工作模式會教你這樣做：
===============================================================================
一：?先試著給1號男生找妹子，發現第一個和他相連的1號女生還名花無主，got it，連上一條藍線
? ? ? ? ? ? ? ? ?
===============================================================================
二：接著給2號男生找妹子，發現第一個和他相連的2號女生名花無主，got it
? ? ? ? ? ? ? ? ?
===============================================================================
三：接下來是3號男生，很遺憾1號女生已經有主了，怎么辦呢？
我們試著給之前1號女生匹配的男生（也就是1號男生）另外分配一個妹子。
(黃色表示這條邊被臨時拆掉)
? ? ? ? ? ? ? ? ? ?
? 與1號男生相連的第二個女生是2號女生，但是2號女生也有主了，怎么辦呢？我們再試著給2號女生的原配()重新找個妹子(注意這個步驟和上面是一樣的，這是一個遞歸的過程)
? ? ? ? ? ? ? ? ? ? ? ?
此時發現2號男生還能找到3號女生，那么之前的問題迎刃而解了，回溯回去
2號男生可以找3號妹子~~~?? ? ? ? ? ? ? ? ?1號男生可以找2號妹子了~~~? ? ? ? ? ? ? ??3號男生可以找1號妹子
? ?
所以第三步最后的結果就是：
? ? ? ? ? ? ? ? ? ? ?
===============================================================================
四：?接下來是4號男生，很遺憾，按照第三步的節奏我們沒法給4號男生騰出來一個妹子，我們實在是無能為力了……香吉士同學走好。
===============================================================================
這就是匈牙利算法的流程，其中找妹子是個遞歸的過程，最最關鍵的字就是“騰”字其原則大概是：有機會上，沒機會創造機會也要上
【code】
[cpp]?view plain?copy在主程序我們這樣做：每一步相當于我們上面描述的一二三四中的一步
[cpp]?view plain?copy總結
以上是生活随笔為你收集整理的匈牙利算法——最大匹配问题详解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 华为数据通信产品VRP操作系统的使用
- 下一篇： leetCode —— 1200.最小绝