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

匈牙利算法

(一)首先明确匈牙利算法是干嘛滴?

    匈牙利算法是解决二部图最大匹配问题滴。

(二)算法的核心思想:不断寻找增广路径,每找到一条增广路径,就通过异或操作使匹配边数加一,直到找不到增广路径,算法结束。

(三)算法的基本步骤:

    (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 }

今天刚学完匈牙利算法,趁热打铁,赶快写篇博客加深一下印象!看不懂你打我!!!不认真看打死你!!!



匈牙利算法