Binary heap

令G = （X,*,Y）是一个二分图，其中，X = {x1,x2,...xm}, Y = {y1,y2,...yn}。令M为G中的任一个匹配。

1）讲X的所有不与M的边关联的顶点标上（@），并称所有的顶点为未被扫描的。转到 2）。

2）如果在上一步没有新的标记加到X的顶点上，则停止。否则转到 3）。

3）当存在X被标记但未被扫描的顶点时，选择一个被标记但未被扫描的X的顶点，比如，xi,用(xi)标记Y的所有顶点，这些顶点被不属于M且尚未标记的边连到xi .现在，顶点xi是被扫描的。如果不存在被标记但未被扫描的顶点，则转到 4）。

4）如果在步骤 3）没有新的标记被标到Y的顶点上，则停止。否则，转到 5）。

5）当存在Y被标记但未被扫描的顶点时，选择Y的一个被标记但未被扫描的顶点，比如yi，用(yi)标记X的顶点，这些顶点被属于M且尚未标记的边连到yi.现在，顶点yi是被扫描的。如果不存在被标记但未被扫描的顶点，则转到 2）。

也可以叙述为：

匈牙利算法 关键在于匈牙利算法的递归过程中有很多重复计算的节点，而且这种重复无法避免，他不能 向动态规划一样找到一个“序”将递归改为递推。

算法中的几个术语说明：

1.二部图：

  如果图G=(V,E)的顶点集何V可分为两个集合X,Y，且满足 X∪Y = V, X∩Y=Φ，则G称为二部图；G的边集用E(G)表示，点集用V(G)表示。 

2.匹配：

  设M是E(G)的一个子集，如果M中任意两条边在G中均不邻接，则称M是G的一个匹配。M中的—条边的两个端点叫做在M是配对的。

3.饱和与非饱和：

  若匹配M的某条边与顶点v关联，则称M饱和顶点v，并且称v是M-饱和的，否则称v是M-不饱和的。 

4.交互道：

  若M是二分图G＝(V,E)的一个匹配。设从图G中的一个顶点到另一个顶点存在一条道路，这条道路是由属于M的边和不属于M的边交替出现组成的，则称这条道路为交互道。 

5.可增广道路：

  若一交互道的两端点为关于M非饱和顶点时，则称这条交互道是可增广道路。显然，一条边的两端点非饱和，则这条边也是可增广道路。 

6.最大匹配：

  如果M是一匹配，而不存在其它匹配M'，使得|M'|>|M|，则称M是最大匹配。其中|M|表示匹配M的边数。 

7.对称差：

  A，B是两个集合，定义A⊕B = (A∪B)\(A∩B), 则A⊕B称为A和B的对称差。 

定理：M为G的最大匹配的充要条件是G中不存在可增广道路。 Hall定理：对于二部图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有： |T(A)| >= |A|

匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为： 1。任给初始匹配M； 2。若X已饱和则结束，否则进行第3步； 3。在X中找到一个非饱和顶点x0，作

   V1 ← {x0},  V2 ← Φ 

4。若T(V1) = V2则因为无法匹配而停止，否则任选一点y ∈T(V1)\V2； 5。若y已饱和则转6，否则做一条从x0 →y的可增广道路P，M←M⊕E(P)，转2； 6。由于y已饱和，所以M中有一条边(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}， 转4；

给定一个二分图(x,y)，x中的点和y中点的连接情况，一个匹配是二分图的子图，其中任一个x中的点只能和最多一个y中的点连接，一个y中的点也只能和一个x中的点连接，最大匹配就是使子图中的边数（我们称为匹配边）最多的匹配。

mat[i,j]记录x中的i和y中j是否可匹配，cov[i]记录y中的已盖点i连着x中的那个点，如果i是未盖点，则cov[i]=0，另外在寻找可增广轨时不能有重复，所以用use[i]记录x中的i是否被访问过。

从x中一未盖点出发，通过交错轨（匹配边和非匹配边交错）找到y中的一个未盖点，然后把这条交错轨上的匹配边和非匹配边交换，则匹配边比原先多了一条，重复以上步骤直到找不到交错轨为止。

伪代码如下：

function can (s:byte):boolean;
 
begin
 
  if use[s] then
 
    exit(false);
 
  use[s]:=true;
 
  for 所有y中的点i do
 
    if mat[s,i] then
 
      if i是未盖点 then
 
      begin
 
        cov[i]:=s;    //i点变成已盖点，交换匹配边和非匹配边
 
        exit(true);
 
      end
 
      else
 
        if can(cov[i]) then
 
        begin
 
          cov[i]:=s;    //交换匹配边和非匹配边
 
          exit(true);
 
        end;
 
  exit(false);
 
end;
 
procedure main;
 
begin
 
  for x中的点i    //i肯定是未盖点
 
    if can(i) then
 
      inc(sum)    //sum是匹配数
 
end;