匈牙利算法（一）：求最大匹配

二分图匹配是图论里一个比较重要的问题，在计算机视觉里也有一些应用，但是网络上这方面的教程似乎都不太完善，要么没有给出算法的推导过程，要么给出的算法和代码实现有一定的差异。所以我整理了一下这方面的内容，尽可能完善一些，就当是做笔记了。

二分图匹配

本文用$G$表示二分图，二分图的两个顶点集合用$X$和$Y$表示，记$n=|X|$，$m=|Y|$。

图上的匹配指点与点之间的匹配，两点之间的匹配可以用连接这两点的边表示，多个匹配就可以用边的集合表示。一个图$G$的匹配是$G$的边子集，且该子集中任意两条边没有公共顶点。一般匹配记为$M$，$M$里的边称为 匹配边。如果一个顶点是$M$中一条边的顶点，则称该顶点为 $M$饱和点，否则称为 $M$非饱和点。比如下图中，红色的边构成的集合就是一个匹配，每个红色的边是一条匹配边，匹配边连接的顶点是饱和点，其余点就是非饱和点。

对于二分图$<X,Y>$而言，如果一个匹配覆盖了$X$的所有顶点，称该匹配为 饱和$X$的匹配。而$G$的所有匹配中边数最多的匹配称为 最大匹配，如果该最大匹配饱和了$G$中所有顶点，则称为 完美匹配，也就是说$G$里的每个顶点都匹配了其它顶点。注意最大匹配肯定存在，但不是唯一的，而完美匹配可能不存在，比如当$|X|\ne|Y|$的时候肯定不存在完美匹配。这里会介绍求最大匹配以及饱和匹配的匈牙利算法，在这之前会介绍几个定理说明最大匹配和饱和匹配存在的充要条件，因为这些算法其实就是从这些定理来的。

交错路

在二分图匹配中最重要的概念是 交错路，它的定义也非常直观：$G$中一条由$M$中的边与非$M$中的边交错形成的路就是$M$交错路。交错路只有起点、终点可能是$M$非饱和点，中间的点都是饱和点，因为中间的点一定邻接一条匹配边，所以肯定是饱和点。根据交错路起点、终点的类别，可以把交错路分为3类：

起点、终点都是$M$饱和点。此时交错路中非匹配边比匹配边少一条
起点、终点其中之一是$M$饱和点。此时交错路中非匹配边数等于匹配边数

这种交错路在后面的证明中经常用到，所以介绍它的一些性质（假设起点属于$X$）：
- 路径长度一定是偶数，因为一半是匹配边，一半是非匹配边
- 匹配边都从$Y$到$X$，非匹配边都从$X$到$Y$
- 终点也属于$X$（起点终点都在一边）
起点、终点都是$M$非饱和点。此时交错路中非匹配边比匹配边多一条，这种交错路称为 增广路，这个增广路和最大流里的增广路是一样的，最大流里的前向边对应非匹配边，反向边对应匹配边。

增广路是一个重要的概念，因为里面的非匹配边比匹配边多一条，所以如果我们找到了一条增广路，只要把里面的非匹配边作为新的匹配，就能得到一个比原来大的匹配。写成公式就是可以通过集合的对称差运算得到新的匹配：
\[M\Delta E(P)=M\cup E(P)-M\cap E(P)\]
且新的匹配比原来的匹配大1。这里$M$是原来的匹配，$E(P)$是增广路$P$的边集。通过这样的路，我们可以扩大现有的匹配，所以叫增广路。另外注意增广路的起点、终点分别属于二分图的两个顶点集内，这个对理解证明有帮助。

Berge定理

理解了交错路和增广路的概念，就可以引入Berge定理，这个定理给出了一个匹配$M$是最大匹配的充要条件。

匹配$M$是最大匹配的充要条件是$G$不包含增广路

这个定理的必要性很好理解，因为存在增广路，则可以增大匹配，所以最大匹配不存在增广路。不过充分性“不包含增广路一定是最大匹配”没有那么显然，用反证法，证明“不是最大匹配的话一定含有增广路”，而证明的方法是从非最大匹配构造一个增广路出来。如果$M$不是最大匹配，则存在更大的匹配$M’$，考虑二者的对称差$M\Delta M’$，由对称差引理，它由路径或偶环组成。对于偶环，属于$M$和$M’$的边的个数相同；对于路径，由于$|M’|>|M|$，一定存在一条路径，里面属于$M’$的边的数量多余属于$M$的边，因此这条路径是$M$的增广路，这样就构造了一个增广路。

这里涉及对称差引理：

设$M_1$和$M_2$是$G$的两个匹配，如果$H=M_1\Delta M_2≠\emptyset$，则$H$由多个路径或偶环组成，且路径或偶环的边交替属于$M_1$和$M_2$（这个导致环一定是偶数条边，所以是偶环，属于$M_1$和$M_2$的边各占一半）

证明也很简单：因为$M_1$和$M_2$是匹配，求对称差之后一个顶点最多与两条边邻接（度数至多为2），并且一个属于$M_1$，一个属于$M_2$。所以$H$一定由路径或环组成，因为只有路径和环的顶点度数不超过2。这里应该好理解，核心是匹配内部的边总是不相交的。

学过最大流算法的肯定觉得这个定理很眼熟，这不就是最大流最小割定理吗？的确是这样，二分图匹配问题是最大流问题的特例，中间的边权全部为1，最大的流在一条边上要么为1，要么为0，分别对应是匹配边和不是匹配边的情况，求最大匹配就是求最大流。

匈牙利算法：求最大匹配

基于Berge定理，我们可以从空匹配开始，不断地去找增广路来扩大匹配，直到不存在增广路为止。而增广路的起点和终点都是非饱和点，所以增广路的搜索可以从一个非饱和点找起，然后利用DFS找到另一个非饱和点就可以了。这样我们就可以得到匈牙利算法：

初始化M为空集
while True:
  find = False

  for x in X:
    if x饱和:  # 从非饱和点x开始尝试找一条增广路
      continue
    
    从x开始找一条增广路P  # 从非饱和点x开始尝试找一条增广路
    if P存在:
      find = True
      利用P更新M  # 扩大匹配
    break

  if not find:  # 不存在增广路了
    break

这个算法还可以改进，改成一个更简单的形式，这也是常见的匈牙利算法实现：

初始化M为空集
for x in X:
  从x开始找一条增广路P
  if P存在:
    利用P更新M

两份代码的区别是后者不需要每次都遍历$X$找一个非饱和点，直到找不到增广路为止，而是只需要把$X$里的非饱和点都遍历一遍去尝试找增广路就可以了。原因是如果从$X$里的一个非饱和点$x$开始找增广路，如果找到了增广路，由于增广路只会让匹配增加1，我们可以证明这个新增的匹配就是$x$的匹配，且其余的$X$里的点原来是饱和点的就还是饱和点，非饱和点还是非饱和点；如果找不到增广路，我们也可以证明它总是找不到增广路。结合这两点就可以理解为什么简单遍历一遍$X$就可以了。

这里涉及两个证明，下面两段分别证明这两点。第一个是从$x$出发找到增广路后扩大匹配，$x$会变为饱和点，而$X$里其它点的饱和性不变。其实这个很好理解，因为通过增广路扩大匹配后，增广路上的所有点都会变成饱和点，所以$x$会变成饱和点，而$X$里其它的点在增广路里的肯定都是饱和点，所以不变，在增广路外的不收影响，所以也不变，这找个例子看看一看就非常直观。另外注意，由于一开始匹配是空集，我们又是遍历$X$来扩大匹配，所以匹配的点都是已经遍历过的，每次找增广路其实都是在往前找，后面还没遍历的点都是非饱和点。

第二点是匹配变化后，是否会使得前面原本找不到增广路的$x$也变得能找到了？答案是不会，如果一个$x$这次找不到匹配，下一次也找不到。如果从一个点$x$出发，没有找到增广路径，那么无论再从别的点出发找到多少增广路径来改变现在的匹配，从$x$出发都永远找不到增广路径。证明用反证法，假如第二次能找到，可以推出第一次就应该找到。记第一次时的匹配为$M$，第二次的为$M’$，且$x$的匹配边属于$M’$而不属于$M$，由于$|M’|>|M|$，于是$M\Delta M’$里存在$M$的增广路，且$x$就在这条增广路上（参考对称差引理）。这意味着从$x$出发是有一条关于$M$的增广路的，第一次就应该找到这条增广路。

到这里求最大匹配已经很直观了。求最大匹配贪心的做法是遍历每个顶点，然后遍历顶点邻接的边，找一个不冲突的作为匹配边，但是冲突是经常存在的，而增广路可以用来解决冲突，匈牙利算法也是遍历$X$里的顶点，但是通过找增广路给顶点$x$找匹配边，是一种更高明的找匹配边的方法。

这里给出匈牙利算法的C++实现：

vector<int> matchY;  // 为了方便，matchY作为全局变量
// findAugPath是寻找增广路的函数，下面会介绍它的实现

int hungary(vector<vector<int>> &W) {
    int n = W.size();
    int m = W[0].size();

    int matchNum = 0;
    matchY = vector<int>(m, -1);  // 初始化匹配
    for(int x=0; x<n; x++) {  // 至多寻找n次增广路
        vector<int> visitedY(m, 0);
        if(findAugPath(W, x, visitedY)) {
          matchNum++;
        }
    }
    return matchNum;
}

这里用矩阵$|X|\times |Y|$的矩阵$W$表示二分图，匹配则用哈希表表示。match[x]=y表示$x$和$y$匹配。图的顶点一般是0到n的整数，所以用数组就可以了，数组初始化为全为-1，表示没有匹配。这里实现上有两种选择：一种是记录match[x]=y，另一种是记录match[y]=x。应该记录后者，因为搜索增广路需要判断一个$y$是不是饱和点，如果保存后者的话就可以直接根据match[y]==-1判断，等于-1就是非饱和点，大于0就是饱和点。所以上面这份代码用一个数组matchY表示。

findAugPath函数用来找从$x$出发的增广路，这种在图上找一条路径用DFS比较方便，搜索的目标是找到$Y$里的一个非饱和点，也就是找到一个matchY[y]==-1的点。另外考虑到我们找的是增广路，从$X$里的点找下一个点都是通过非匹配边得到的，这需要遍历，而从$Y$里的点找下一个点可以直接由matchY[y]得到。于是就有了这样的代码：

bool findAugPath(vector<vector<int>> &W, int x, vector<int> &visitedY) {
    int m = W[0].size();

    // 从x出发找一条增广路
    for(int y=0; y<m; y++) {
        if(visitedY[y]) continue;
        if(W[x][y] > 0) {
            visitedY[y] = true;
            if(matchY[y] == -1 \|\| findAugPath(W, matchY[y], visitedY)) {
                // 这里有短路求值，合并了两种情况
                matchY[y] = x;  // 回溯的时候，隐式的根据匈牙利树修改匹配
                return true;
            }
        }
    }
    return false;
}

这里修改匹配的部分很巧妙，不需要求对称差，找到增广路后，利用DFS的回溯把匹配修改了就行。

因为DFS如果找不到就会回溯，这种情况下，DFS搜索交错路的过程构成一颗树，称为 交错树。交错树也由匹配边和非匹配边交错组成，如下图所示。如果交错树里存在非饱和叶子节点，那么它可以扩大匹配。如果交错树的叶子节点都是饱和点，那么它称为 匈牙利树。如果只能找到匈牙利树，说明不存在增广路。

每次找增广路延长，需要找$n$次，每次需要一次DFS（BFS也行，复杂度更低），复杂度$O(nm)$，总复杂度是$O(n^2m)$，对于$n=m$这种常见的情形就是$O(n^3)$。一个显然的改进是类似于Dinic算法那样通过BFS一次找多个增广路，其实也有这样的算法，好像叫Hopcroft-Karp算法。Leetcode上有一道关于匹配的题LCP 04. 覆盖，可以尝试做一下。

Hall定理

前面介绍的是最大匹配的求法，下面要介绍饱和$X$的匹配的求法，在这之前需要介绍相关的Hall定理：

$G$中存在饱和$X$的匹配（也叫$X$到$Y$的匹配）的充要条件是$\forall S\subseteq X,|N(S)|\ge|S|$，其中$N(S)$指与$S$中的顶点邻接的顶点的集合。

Hall定理说的是如果要存在饱和$X$的匹配，$X$里每个点相邻的点要比较多才行，不然匹配很容易冲突。$|N(S)|\ge |S|$说明一定不存在冲突，因为$S$里的每个点都能在$N(S)$找到一个与之匹配的点。

下面介绍Hall定理的证明。证明必要性很简单，与$S$里的顶点匹配的顶点至少有$|S|$个，所以$|N(S)|≥|S|$，或者反过来理解，如果$|N(S)|<|S|$，那么肯定存在冲突，也就不存在饱和$X$的匹配了。充分性的证明比较麻烦，个人感觉比较直观的做法是构造一个饱和匹配出来，毕竟条件是不存在冲突，但是构造可能比较困难，所以没看到这样的证明。常见的证法是用反证法，整体思路是如果$X$还有非饱和点，就能存在一个$S$，满足$|N(S)|=|S|-1$，与$|N(S)|≥|S|$矛盾。

假设不存在饱和$X$的匹配，选择包含$X$最多顶点的一个匹配，也就是取一个最大匹配，$X$中肯定存在不属于该匹配的顶点$u$，即$u$是非饱和点。
记从$u$出发的所有交错路的顶点集合的并集为$A$。

这里举个例子，假设$u$对应上图中的顶点2，从$u$出发的所有交错路的并集是$\lbrace 2,8,3,9,4\rbrace$。
记$S=X\cap A$，$T=Y\cap A$。

这里的$S$和$T$就是$A$属于$X$和$Y$里的部分。其实$A$去掉$u$，剩下的顶点都是匹配的，里面的匹配边是$T$和$S-\lbrace u\rbrace$一一映射，所以$|S|=|T|+1$。结合上图中的例子也很直观，$S=\lbrace 2,3,4\rbrace$，而$T=\lbrace 8,9 \rbrace$。

前面取$A$的作用就是为了说明存在这个$S$，然后我们要证明$N(S)=T$来得到矛盾。证明集合相等可以通过证明$T\subseteq N(S)$以及$N(S)\subseteq T$得到：
- 显然有$T\subseteq N(S)$，因为$T$是增广路里的，就是通过找$S$的邻域得到的。
- 因为找不到增广路了，所以$N(S)$里的点都是饱和点，进一步由于$T$里的点也都是饱和点，可以得到$N(S)-T$里的点都是饱和点。如果$N(S)-T$不是空集，记$v$是里面的一个元素，无论$v$是$S$中谁的邻居，都存在一条从$u$到$v$的交错路，这和$A$的取法矛盾了，所以$N(S)-T$肯定是空集，所以$N(S)\subseteq T$。
  
  这里有点抽象，再举个例子。给上图的例子再加一条边使得$N(S)-T$不是空集：
  
  添加的边连接了$2$和$a$，那么$2\rightarrow a$也是一个增广路，但是$A$没有包含，和$A$是所有增广路顶点的集合矛盾了。
综上有$N(S)=T$，$|N(S)|=|S|-1$，与条件$|N(S)|≥|S|$矛盾。

整体证明最核心的部分是考虑了从非饱和点$u$出发的所有交错路的这样一个子图，它的$S$和$T$比较特殊，是存在冲突的部分。

基于Hall定理很容易得到一些推论，比如$k$正则二分图存在完美匹配、树至多存在一个完美匹配等等。与二分图匹配相关的定理还有一些，比如Tutte定理等，这里就不介绍了。

饱和匹配的存在性判断

如何写程序判断饱和匹配的存在性？用匈牙利算法求最大匹配，然后判断是否饱和当然是没问题的，不过利用Hall定理可以得到一个更快的解法。结合Hall定理，对求最大匹配的匈牙利算法稍作修改就能判断饱和匹配是否存在。Hall定理的证明指出了冲突的部分是从一个非饱和点出发的所有交错路这个子图，而匈牙利算法就是从非饱和点出发搜索增广路，如果搜索失败了，那么搜索过的顶点不就刚好对应了这个子图吗？所以只要有一个顶点搜索失败，就说明不存在饱和匹配：

初始化M为空集
for x in X:
  从x开始找一条增广路P
  if P存在:
    利用P更新M
  else:
    return False

其实结合前面对匈牙利算法的理解，一个非饱和点如果找不到增广路，之后就总是找不到的，因而不存在饱和匹配。这么理解也是可以的，但是Hall定理给了一个更深刻的理解，后面求最优匹配的KM算法要用到。另外，从匈牙利算法可以很容易的得到$S$和$T$：DFS过程中访问过的顶点，在$X$中的就是$S$，在$Y$中的就是$T$，实现的时候可以用visitedX和visitedY这两个数组记录。

最大匹配与最大流的关系

二分图匹配是最大流问题的一个特例，匈牙利算法是FF算法在特殊图上的一个特例，如上图所示（其实匈牙利算法先于FF算法提出，应该说FF算法是匈牙利算法的扩展）。二分图和最大流的增广路其实是一样的，最大流里面的残余图的前向边对应非饱和边，反向边对应饱和边。交错路径里的饱和边会被撤销，原因就在于它对应反向边，且权重总是为1。如果用Dinic算法求二分图匹配，复杂度是$O(\sqrt nm)$，比匈牙利算法快，但是空间开销更大。不过匈牙利算法独特的地方在于可以边运行，边判断饱和匹配的存在性。

二分图的点覆盖

记$K$是$G$的顶点子集，若$G$中任意一条边都至少有一个顶点属于$K$，则$K$是$G$的一个 点覆盖，简称覆盖。所以点覆盖指的是点覆盖边。在$G$的所有点覆盖中，顶点数最少的那个点覆盖$K$称为 最小点覆盖（或者简称 最小覆盖）。在一般的图上求最小点覆盖是NP难问题，但是二分图上不是。

Konig定理

二分图中，最大匹配的边数等于最小覆盖的顶点数。

这个的证明很简单，分两步。先证明最小覆盖≥最大匹配：最大匹配没有邻接的边，要覆盖所有的边，每个匹配边至少要有一个顶点在点覆盖里。然后证明等于可以取到：可以从最大匹配构造一个点覆盖（构造方法看后面），二者大小相等，于是得证。

Konig定理有一些推论：

记$M$是$G$的匹配，$K$是$G$的覆盖。若$|M|=|K|$，则$M$是最大匹配，$K$是最小覆盖
矩阵的行或列称为线。布尔矩阵中，包含了所有1的最少线数，等于独立1的最大数目。

第一点很显然，这里对第二点进行说明。一个布尔矩阵对应一个二分图，比如对于矩阵$A$，$a_{ij}$为1就把点$i$和点$j$连起来，也就是一个矩阵里的元素对应一条边。一条线则对应一个顶点（行对应$X$里的顶点，列对应$Y$里的顶点），最少线数就是最小覆盖。如果几个1在同一个线上，那么这些1里只有一个算独立的1，独立的1有不同的选择（相当于选择不同的边构成一个匹配）。在整个矩阵里，不同的独立1的选择会导致有不同的独立的1的个数，这个就是独立1的数目（就是匹配的大小）。独立1的最大数目就是最大匹配，因为一个1对应一条边，多个独立的1构成一个匹配。所以这个引理就是矩阵形式的Konig定理。

求最小点覆盖

这里介绍求出了最大匹配后，如何从这个最大匹配来构造一个点覆盖。分为三步：

记录$X$的所有非饱和点，如果没有非饱和点，则$X$就是一个最小点覆盖。
从$X$的所有非饱和点出发寻找交错路，一直到寻找不到新的点。这样可以寻找到多条交错路，且起始点为非饱和点，终点为饱和点（且回到$X$）。这些交错路可能有重合的边。记录所有交错路的顶点集合，根据属于$X$还是属于$Y$，分为$S$和$T$。
$(X-S)\cup T$就是最小点覆盖。

下图是一个例子：

下面证明为什么$(X-S)\cup T$是最小点覆盖，一是要证明这是一个覆盖，二是要证明它的大小等于$|M|$，所以是最小点覆盖。

为什么这是一个覆盖，即为什么覆盖了所有边？考虑一条边的2种情况：如果它在交错路里，显然被$T$覆盖；如果它不在交错路里，可以证明它被$X-S$覆盖。反证法，如果边$<x,y>$不被$X-S$覆盖，说明$x$在$S$里。对$x$进行分类讨论： $x$是非饱和点，那么$y$肯定也是非饱和点，不然就会出现在交错路里。这样的话，这条边可以构成一个新的匹配边，与$M$是最大匹配矛盾； $x$是饱和点，但这是不可能的，因为$S$里的饱和点都是由于在交错路里才会被添加进来的综上，它不可能不被$X-S$覆盖。

为什么大小等于$|M|$？因为$(X-S)\cup T$刚好覆盖了所有匹配边。匹配边的两个顶点要么都在$S$和$T$里，要么都不在$S$和$T$里。因为匹配边要么在找到的交错路里，要么不在，所以交错路里的匹配边两个端点都在$S$和$T$里，而交错路之外的匹配边都不在$S$和$T$里。$X-S$相当于取反，使得对于任意的匹配边，刚好只有一个顶点在$(X-S)\cup T$里（交错路里的匹配边有一个顶点在$T$里，交错路外的匹配边则有一个顶点在$X-S$里），所以$(X-S)\cup T$刚好覆盖了所有匹配边，因而大小等于$|M|$。

总结

本文介绍了二分图中的匹配与点覆盖的概念与相关定理，主要是Berge定理和Hall定理，以及求最大匹配以及饱和匹配的匈牙利算法。除此之外，也介绍了与最大匹配等价的最小覆盖问题的求法。

下篇匈牙利算法（二）：求最优匹配