圖采用矩陣存儲，下標從1開始。
匈牙利匹配算法的理論和證明不復雜，就是不斷尋找兩個端點都是未浸潤點的交替路徑，把路徑上的邊匹配狀態全部取反。每次操作，圖的匹配數都增加1。為方便描述，將二部圖劃分為X和Y兩個部集。
此算法有幾個性質：
1.算法只需以某一個部集（可以是X或Y）中的所有未浸潤點為交替路徑的起始點，展開尋找。
2.X中的某個點，只有在以它為起始點進行過交替路徑搜索后，才有可能變為浸潤點。
3.以X中的某個點為起始點，如果無法找到交替路徑，那么以后不論何時以它為起始點，都不可能找到交替路徑。
4.據1,選擇處理X集，由2,3知X集中的所有點最多只需處理一次。
偽代碼：
1 SEARCH(Vi):
2 SEARCH AUGMENT PATH STARTING FROM Vi
3 IF FOUND THEN RETURN TRUE
4 ELSE RETURN FALSE
5 MATCHING(G(X,Y)):
6 ANS:=0
7 FOR EACH VERTEX Vi IN SET X
8 T:=SEARCH(Vi)
9 IF T=TRUE
10 ANS:=ANS+1
11 END IF
12 END FOR
尋找交替路徑這個過程有
BFS和
DFS兩種方式。
DFS:
1 int w[NX][NY]; //X中的點到Y中的點的連接矩陣,w[i][j]是邊<Vxi,Vyj>的權
2 int m[NY]; //Vyi的匹配對象
3 int v[NY]; //在一次DFS中，Vyi是否被訪問過
4 bool dfs(int k){ //以Vxk為起點找交替路徑
5 int i;
6 for(i=1;i<=N;i++){
7 if(!v[i] && w[k][i]){ //如果Vyi未訪問過，而且Vxk,Vyi有邊連接
8 v[i]=1;
9 if(!m[i] || dfs(m[i])){ //如果Vyi是未浸潤點，或者以Vyi原來的匹配點為起始，有擴張路徑
10 m[i]=k;
11 return true; //擴張成功
12 }
13 }
14 }
15 return false;
16 }
這個算法也可以從類似“貪心”的角度理解：一個X中的點Vx0，如果找到某個能到達的Y點Vy0，就暫時把它“據為己有”，然后看Y的“原配X點”還能不能找到別的Y點配對，如果能，那么Vx0和Vy0就配對成功，否則不成功，Vx0繼續尋找別的Vy。
BFS:
這是我在某些算法書上看到的BFS版本，需要用變量（或變量數組）tag記錄擴展目標。代碼中，我改為用que[i]的bit1記錄：
1 int w[NX],ma[NY];
2 int que[NX+NY],pq,sq; //廣搜隊列
3 int pax[NX],pay[NY]; //記錄交替路徑
4 bool bfs(int r){
5 int i,j,k,tag; //tag，記錄交替路徑的下一步要擴展X中的點(tag==1時)，還是Y中的點(tag==0時)
6 memset(pax,0,sizeof(pax));
7 memset(pay,0,sizeof(pay));
8 que[0]=(r<<1);
9 pq=0; sq=1;
10 while(pq<sq){
11 k=que[pq]>>1; tag=que[pq]&1;
12 if(tag==0){ //process set X, look for unvisited vex in Y
13 for(i=1;i<=N;i++){
14 if(!pay[i] && w[k][i]){
15 pay[i]=k;
16 if(!ma[i]){ //是未浸潤點，擴展路徑搜索完畢
17 for(j=i;j;j=pax[pay[j]]){
18 ma[j]=pay[j];
19 }
20 return true;
21 }
22 else{ //這個Y點不是未浸潤點,入隊
23 que[sq++]=(i<<1)|1;
24 }
25 }
26 }
27 }
28 else{ //Vyk不是未浸潤點，路徑必須沿著它所在的匹配邊擴展
29 que[sq++]=(ma[k]<<1);
30 pax[ma[k]]=k;
31 }
32 pq++;
33 }
34 return false;
35 }
其實，在遇到浸潤的Vyi時，由于下一步只能沿著它的匹配點Vxj走，即排隊輪到Vyi時，必定是Vxj被加入隊列。因此，只要令隊列que僅存放X集的點，每次遇到浸潤的Vyi，把它的匹配點Vxj加入隊列。這樣就省去了分支，減小了代碼量。
實現：
1 int w[NX],ma[NY];
2 int que[NX+NY],pq,sq;
3 int pax[NX],pay[NY];
4 bool bfs(int r){
5 int i,j,k;
6 memset(pax,0,sizeof(pax));
7 memset(pay,0,sizeof(pay));
8 que[0]=r;
9 pq=0; sq=1;
10 while(pq<sq){
11 k=que[pq++];
12 for(i=1;i<=N;i++){
13 if(!pay[i] && w[k][i]){
14 pay[i]=k;
15 if(!ma[i]){ //free vex, augment path found
16 for(j=i;j;j=pax[pay[j]]){
17 ma[j]=pay[j];
18 }
19 return true;
20 }
21 else{ //add Y's matched vex to que
22 pax[ma[i]]=i;
23 que[sq++]=ma[i];
24 }
25 }
26 }
27 }
28 return false;
29 }
顯然，單純的匹配問題，BFS和DFS復雜度都是O(mn)，但DFS編碼難度小很多。
還有一種Hopcroft-Karp算法，復雜度是O(msqrt(n))，只能用BFS實現，暫時還沒深入研究。
然而，解決帶權匹配問題時，DFS只能做到O(n^4)，而BFS可以做到O(n^3)。
posted on 2009-02-15 21:55
wolf5x 閱讀(1790)
評論(0) 編輯 收藏 引用 所屬分類:
algorithm