二分图匹配 匈牙利算法, 最小路径覆盖.


 二分图匹配-匈牙利算法

程序可以参考

http://blog.csdn.net/Fandywang_jlu/archive/2008/03/20/2201351.aspx

分析参考

http://imlazy.ycool.com/post.1603708.html

最小路径覆等价于二分图最大匹配, 具体的解释可以参考

http://hi.baidu.com/ufo008ahw/blog/item/363efdfd718e8443d7887de0.html

 

贴上程序

 

#include <stdio.h>
#include 
<memory.h>

int    n, m, match[100];                        //二分图的两个集合分别含有n和m个元素,match[i]存储集合m中的节点i在集合n中的匹配节点,初值为-1。
bool    visited[100], map[100][100];                 //map存储邻接矩阵。

bool DFS(const int &k)
{
      
for(int i = 0; i < m; i++)    
           
if( map[k][i] && !visited[i]    )    //有从k到i的边,并且i尚未访问过
          {
               visited[i] 
= true;    //为什么不放在下面那个if里面??
             if( match[i] == -1 || DFS(match[i]) )   //寻找是否为增广路径, i尚未有匹配边或者从i的匹配顶点一直找下去能成功,说明成功找到了一个增广路径,修改i的匹配点为k即可
         
           match[i] 
= k;            //路径取反操作。
           return true;
              }

          }

       
return false;
}

 
int main(void)
{
    
//  init map, n, m
    for(int i=0;i<100;i++)
    
for(int j=0;j<100;j++)
        map[i][j] 
= 0;
    
    n
=5;    m=4;
    
int theEdge[][2]={
     
{0,0}{0,1},{1,2},{3,1},{4,2}
    }
;
    
    
int numEdge = sizeof(theEdge)/sizeof(theEdge[0]);
    printf(
"numEdge %d\n", numEdge);
    
for(int i=0; i<numEdge; i++)
        map[theEdge[i][
0]][theEdge[i][1]] = 1;
    
    
//. DFS
   int     count = 0;
   memset(match, 
-1sizeof(match));
   
for(int i = 0; i < n; i++)
   
{    //以二分集中的较小集为n进行匹配较优
         memset(visited, 0,sizeof(visited));    //每对一个节点i做dfs都要首先初始化visited数组
        if( DFS(i) )     ++count;    //count为匹配数
   }

   
   
// print result
   printf("num of matched: %d\n", count);
   printf(
"the match table:\n");
   
for(int i=0; i<m; i++)
        
if(match[i] != -1)
            printf(
"%d %d\n", match[i] , i);
//
    return 0;
}

 

Powered by Jekyll and Theme by solid

本站总访问量