1、網(wǎng)絡(luò)流

　　給定一個(gè)二分圖G = （X， E， Y）。構(gòu)造與G對(duì)應(yīng)的網(wǎng)絡(luò)G‘， 構(gòu)造方法如下：

（1）增加一個(gè)源點(diǎn)s， 一個(gè)匯點(diǎn)t 。

（2）從s向X的每個(gè)頂點(diǎn)引一條有向邊，從Y的每個(gè)頂點(diǎn)向t引一條有向邊。

（3）將原圖G的每一條邊改為從X指向Y的有向邊。

（4）讓所有的邊容量為1 。

然后求最大流，就是二分圖的最大匹配邊數(shù)。

　　2、匈牙利算法

??? 首先定義增廣路：若P是圖G種一條聯(lián)通兩個(gè)未匹配定點(diǎn)的路徑，并且屬于M的邊和不屬于M的邊（已匹配的邊和未匹配的邊）在P上交替出現(xiàn)，則稱(chēng)P為相對(duì)于M的一條增廣路。特別地，當(dāng)一邊（v, v^'）兩端點(diǎn)均為非M-頂點(diǎn)，通路（v, v^'）亦稱(chēng)為增廣路。

算法具體實(shí)現(xiàn)：

???（1）首先用（*）標(biāo)記X中所有的非M-頂點(diǎn)，然后交替進(jìn)行步驟（2），（3）。

????（2）選取一個(gè)剛標(biāo)記（用（*）或在步驟（3）中用（y_i）標(biāo)記）過(guò)的X中頂點(diǎn)，例如頂點(diǎn)x_i，然后用（x_i）去標(biāo)記Y中頂點(diǎn)y，如果x_i與y為同一非匹配邊的兩端點(diǎn)，且在本步驟中y尚未被標(biāo)記過(guò)。重復(fù)步驟（2），直至對(duì)剛標(biāo)記過(guò)的X中頂點(diǎn)全部完成一遍上述過(guò)程。

????（3）選取一個(gè)剛標(biāo)記（在步驟（2）中用（x_i）標(biāo)記）過(guò)的Y中結(jié)點(diǎn)，例如y_i，用（y_i）去標(biāo)記X中結(jié)點(diǎn)x，如果y_i與x為同一匹配邊的兩端點(diǎn)，且在本步驟中x尚未被標(biāo)記過(guò)。重復(fù)步驟（3），直至對(duì)剛標(biāo)記過(guò)的Y中結(jié)點(diǎn)全部完成一遍上述過(guò)程。

（2），（3）交替執(zhí)行，直到下述情況之一出現(xiàn)為止：

????（Ⅰ）標(biāo)記到一個(gè)Y中頂點(diǎn)y，它不是M-頂點(diǎn)。這時(shí)從y出發(fā)循標(biāo)記回溯，直到（*）標(biāo)記的X中頂點(diǎn)x，我們求得一條增廣路。設(shè)其長(zhǎng)度為2k+1，顯然其中k條是匹配邊，k+1條是非匹配邊。

????（Ⅱ）步驟（2）或（3）找不到可標(biāo)記結(jié)點(diǎn)，而又不是情況（Ⅰ）。

????（4）?當(dāng)?（2），（3）步驟中斷于情況（Ⅰ），則將增廣路中非匹配邊改為匹配邊，原匹配邊改為非匹配邊（從而得到一個(gè)比原匹配多一條邊的新匹配），回到步驟（1），同時(shí)消除一切現(xiàn)有標(biāo)記。

????（5）對(duì)一切可能，（2）和（3）步驟均中斷于情況（Ⅱ），或步驟（1）無(wú)可標(biāo)記結(jié)點(diǎn)，算法終止（算法找不到增廣路）。

轉(zhuǎn)自：http://hi.baidu.com/sysucs/blog/item/c1c58dee4c5247282df53484.html

?

　　2-21：

　　今天做一下補(bǔ)充，在Matrix67 大神的解釋：

　　說(shuō)穿了，就是你從二分圖中找出一條路徑來(lái)，讓路徑的起點(diǎn)和終點(diǎn)都是還沒(méi)有匹配過(guò)的點(diǎn)，并且路徑經(jīng)過(guò)的連線是一條沒(méi)被匹配、一條已經(jīng)匹配過(guò)，再下一條又沒(méi)匹配這樣交替地出現(xiàn)。找到這樣的路徑后，顯然路徑里沒(méi)被匹配的連線比已經(jīng)匹配了的連線多一條，于是修改匹配圖，把路徑里所有匹配過(guò)的連線去掉匹配關(guān)系，把沒(méi)有匹配的連線變成匹配的，這樣匹配數(shù)就比原來(lái)多1個(gè)。不斷執(zhí)行上述操作，直到找不到這樣的路徑為止。

?

　?? 下面是匈牙利算法的實(shí)現(xiàn)：

?

1 bool dfs(int t) {
2 for(int i = 1; i <= stu; i++) {
3 if(!usd[i] && g[t][i]) {
4 usd[i] = true;
5 if(Link[i] == -1 || dfs(Link[i])) {
6 Link[i] = t;
7 return true;
8 }
9 }
10 }
11 return false;
12 }
13
14 for(i = 1; i <= cou; i++) {
15 memset(usd, 0, sizeof(usd));
16 if(dfs(i)) ans++;
17 }

　

?

?

?

??????????? ????????? ?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

總結(jié)

以上是生活随笔為你收集整理的二分图最大匹配问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。