图采用矩阵存储，下标从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 阅读(1771)
评论(0) 编辑 收藏 引用 所属分类:
algorithm