一个图的“匹配”是该图的边的这样一个子集：一条边的顶点不可能出现在另一条边中。

由此我们可以得到几个重要概念：

  • 完美匹配：一个包含了所有顶点的匹配
  • 最大匹配：包含边数最多的匹配
  • 极大匹配：无法再继续添加边的匹配
  • 交替路径：从未匹配结点出发，依次经过“非匹配边”、“匹配边”、“非匹配边”……形成的路径
  • 增广路径：如果一条交替路径的终点也是未匹配顶点，那么这条路径就是增广路径

仅仅从定义上，我们可以很容易得出一些包含关系：极大匹配 ⊆ 最大匹配 ⊆ 完美匹配

完美匹配是否存在受结点的数量影响，所以我们一般讨论最大匹配。

当然，在匹配算法中最重要的概念就是增广路径。它是算法的核心。

偶图匹配

为什么从偶图开始？原因是在偶图中形成的环一定是偶数额顶点（或边数），不需要考虑到奇环的情况，便于我们增广路径的分析。

即使考虑一般的情况，整个算法的核心思想就是：

先尽可能的扩大匹配的范围，获得一个极大匹配。

然后再反复寻找增广路径，通过将路径中的“匹配边”和“未匹配边”反转，获得新的匹配。

直至无法找到增广路径，一个图的最大匹配也就找到了。

每次找到增广路径时，匹配的边数就会加 1 .

所以在设计算法时，我们可以先随机添加边（前提是两个顶点均未匹配）。然后再反复地检查增广路径。

关于增广路径的寻找有DFS和BFS两种方法，这里提供DFS版本：

Algorithm: Find_Augmenting_Path(graph, vertex, visited, match)
Input:
    - A graph stored in adj
    - a unmatched vertex
    - a visted array to track visited vertices for current search
    - a match array where match[v] stores the mate of v
Output: TRUE if an sugmenting path is found and matching is updated, false otherwise

Fn Find_Augmenting_Path(G, u, visited, match)
    for each vertex v in G.adj[u]:
        if (visited[v]==FALSE):
            visited[v] = TRUE

            if (match[v]==NIL): // v is unmatched, then we find the path
                match[v] = u    // match u and v
                return TRUE
            else:
                partner=match[v]
                if(Find_Augmenting_Path(G, partner, visited, match) == TRUE):
                    match[v] = u // the partner has found a new match, v is free for u
                    return TRUE
                endif
            endif
        endif
    endfor

    return FALSE

这个过程可以这样用舞伴理解：

一群男女各自寻找自己认识的异性舞伴，一开始都是比较随机的，会剩下几个落单的。

我们从某个落单者开始，Ta先去寻找自己认识的异性，如果对方有了舞伴，那么我们就从对方的舞伴开始，把TA当作落单者去寻找新的认识的落单异性。这个链条一直传递下去，如果最后有人找到了，那么TA可以直接断开原先的关系，找到新的舞伴。这个过程反向传播到最开始，就让我们最初的落单者可以和TA寻找的舞伴配对了。

一点优化

寻找增广路径的DFS算法对内存的开销比较大，所以为了提高性能，我们尽量在初始化阶段就尽可能获得多的边数。

一个思路是：总是从度数最少点开始寻找匹配，因为后面度数越高的点能够寻找到匹配的成功率更高。

非常稠密图中的完美匹配

非常稠密图通常指边数非常接近与完全图边数的图。假设有 n 个点，那么每个点的度数至少为 n/2 .

非常稠密图的一个好处是，几乎必然能够找到一条哈密尔顿回路，我们可以直接间隔地取回路中的边作为匹配边，由此便得到了完美匹配。

一个比较高效的方法是：

  1. 最开始尽可能的拓展一个回路，让这个回路包含较多的结点，得到P=(v1, v2, … vk)
  2. 对于未在回路中的点 u ，由于图十分稠密，我们一定能够在圈上找到相邻两点 vi, vj，使得存在u与这两个点分别相邻
  3. 将u插入到vi和vj之间

最终我们在O(n²)时间内就可以完成。

一般图的匹配算法

以上讨论的都是两种比较简单的图，但是考虑一般的图，就需要考虑到前文提过的奇环情况。这里并不打算实现相关算法，如果有兴趣，可以去了解一下 Blossom Algorithm，这个算法是解决一般图完美匹配的通用标准。

此外，对于偶图的匹配算法，Hopcroft-Karp Algorithm提供了一种处理大规模数据时的高效方法。