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

二分图匹配-匈牙利算法

程序可以参考

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, -1, sizeof(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;

}

Published on Jun 26, 2009 in categories

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

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