首页 > 代码库 > 匈牙利算法

匈牙利算法

匈牙利算法其实就是一种递归,是由匈牙利数学家提出,该算法的核心就是寻找增广路经,它是一种用增广路径求二分图最大匹配的算法。
 其时间复杂度为O(v*e),v为左边的个数,e为右边的个数。

 

这是一个二分图,现在求这个图的最大匹配。

技术分享

(1)

技术分享

最开始的匹配会得到

  1->A;  2->B;

(2)

当对3进行匹配时,会发现3所对应的A和B 都已经被匹配完毕。此时为了大局着想,1和2必须为3让位。

首先1把A让给3,即 3->A;

此时会发现1还有可以用来对应的,于是2把B让位给1,即1->B;

然后2呢也会有一个与其对应的字母C,所以3->C;

技术分享

(3)

此时再来看4这个数字,由于他只能跟C进行匹配,所以假设4->C;

那么1,2,3就没有足够的字母来与其对应,所以4并没有能找到预期匹配的项。

所以这个二分匹配图的最大匹配就为3

 

算法实现:

1 //首先要进行初始化,将可以进行匹配的记录下来 
2 void init()
3 {
4     for(int i=0;i<n;i++)
5     {
6         scanf("%d %d",&a,&b);
7         g[a][b]=1;//a和b是可以进行匹配的 
8     } 
9 }

然后就是对每个的数字进行遍历,寻找最大匹配的数量

 1 for(int i=1;i<=4;i++)
 2 {
 3     memset(mark,0,sizeof(mark));
 4     //将字母进行初始化,也就是所有的字母没有被选过
 5     if(find(i))
 6     {
 7         ans++;
 8     } 
 9 } 
10 //输出结果 

其中该算法的核心就是进行多次匹配的时候的“”了。

 1 int find(int x)
 2 {
 3     for(int i=1;i<=4;i++)
 4     {
 5         if(g[x][i]==1&&mark[i]==0)
 6         {
 7             mark[i]=1;
 8             //如果字母没有被匹配,而且可以通过更改之前匹配的项
 9             //让其可以得到一个对应的字母,那么就返回1 
10             if(zm[i]==0||find(zm[i]))
11             {
12                 zm[i]=x;
13                 return 1;
14             }
15         }
16     }
17     return 0;
18 }

 

匈牙利算法