首页 > 代码库 > 匈牙利算法
匈牙利算法
匈牙利算法其实就是一种递归,是由匈牙利数学家提出,该算法的核心就是寻找增广路经,它是一种用增广路径求二分图最大匹配的算法。
其时间复杂度为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 }
匈牙利算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。