首页 > 代码库 > 匈牙利算法
匈牙利算法
（一）首先明确匈牙利算法是干嘛滴？
匈牙利算法是解决二部图最大匹配问题滴。
（二）算法的核心思想：不断寻找增广路径，每找到一条增广路径，就通过异或操作使匹配边数加一，直到找不到增广路径，算法结束。
（三）算法的基本步骤：
(1)任取二部图G(X,Y)的匹配M，若M饱和X，则停止。若M不能饱和X，则取X的未标记的M非饱和点x。（标记的点表示经过此点不存在增广路）令S={x},T= ?.(T集合中的点表示N（S）中已经加入增广路的点）(当不存非饱和点或者所有非饱和点都被标记,算法结束)
(2)若N(S)=T，（S集合中的所有点的对应项都是已经走过的的点）则返回(1)，即无经过x的增广通路，标记x。否则，取y ∈N(S)-T。
(3)若y是M饱和的，则存在z ∈X-S使yz ∈M.令S=S∪{z}，T=T∪{y}，转入(2)。若y是M非饱和的，则G中存在以x为起点y为终点的M增广通路P。用令M=M异或EP，即将这条增广路上的已匹配边与未匹配边对换，得到比原来匹配数多一的新匹配，转入(1).
（四）算法的核心结构
1 void hungary()//匈牙利算法
2 {
3 for i->1 to n
4 if (从i的对应项出有可增广路)
5 匹配数++;
6 输出 匹配数;
7 }
8 bool findpath(k)//寻找从k出发的对应项出的可增广路
9 {
10 while (从邻接表中列举k能关联到顶点j){
11 if (j不在增广路上){
12 把j加入增广路;
13 if (j是未匹配点 或者 从j的对应项出发有可增广路)
14 修改j的对应项为k;//也就是说边(k,j)匹配，j对应匹配到k上
15 则从k的对应项出有可增广路,返回true;
16 }
17 }
18 }
19 则从k的对应项出没有可增广路,返回false;
20 }
（五）算法的核心代码
1 bool findpath(int x)
2 {
3 visx[x] = true;
4 for(int y = 1 ; y <= ny ; ++y){
5 if(!visy[y] && (lx[x] + ly[y] == G[x][y])){
6 visy[y] = true;
7 if(match[y] == -1 || findpath(match[y])){
8 match[y] = x;
9 return true;
10 }
11 }
12 }
13 return false;
14 }
今天刚学完匈牙利算法，趁热打铁，赶快写篇博客加深一下印象！看不懂你打我！！！不认真看打死你！！！
匈牙利算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。