霍普克罗夫特—卡普算法

霍普克罗夫特—卡普算法（Hopcroft–Karp algorithm）求解无权二分图的最大基数匹配。图的顶点分成左右两部，边只连接不同部；匹配是一组两两不共享端点的边。目标是让匹配的边数最多，并非仅找到一个无法直接再加边的极大匹配。

相对于当前匹配，交替路径轮流经过非匹配边和匹配边。若路径两端都是尚未匹配的顶点，它就是增广路径。把路径上原有匹配边移出、其余边加入，就会多出一条匹配边，同时维持每个顶点最多参与一次配对。没有增广路径是达到最大基数的判据。

参考：[1]

设左部有甲、乙，右部有一、二，允许边为甲—一、甲—二、乙—一。若当前只匹配甲—一，不能直接把乙—一加进去，因为顶点一已被占用。但乙—一—甲—二是一条增广路径：移除甲—一，再加入乙—一和甲—二，匹配数便从1增加到2。

这个例子说明，增广不只是为未配对顶点挑一个空位，还会重新安排已有配对。朴素算法每次找到一条这样的路径就更新；霍普克罗夫特—卡普算法的改进在于，把同一阶段可利用的最短路径成批处理，减少重复搜索整个图的次数。

参考：[1]

先将非匹配边定向为从左到右，将匹配边定向为从右到左。从左部所有未匹配顶点同时作广度优先搜索，建立距离层次，并确定到达右部未匹配顶点的最短距离。随后只沿符合层次的边搜索最短增广路径。

深度优先搜索寻找一组顶点互不相交的最短增广路径，要求这组路径已经极大，即不能再加入一条与已有路径都不相交的同类路径，而不必求出条数最多的路径组。每条路径带来一次增广；互不相交使这些改变不会争夺同一个端点。更新匹配后重新分层，直至再也找不到增广路径。

参考：[1] [2]

用邻接表并妥善记录本阶段已经处理的边，分层和批量搜索可在O(V＋E)时间完成。完成一个阶段后，最短增广路径长度严格增加；当路径已很长时，与最优匹配相比尚缺的边数又很少。结合这两种进展，可将阶段数界定为O(√V)。

因此常见总时间界为O((V＋E)√V)，其中V、E分别是顶点数和边数；若预先排除孤立顶点并单独计入读入成本，主体计算常写成O(E√V)。这是最大基数问题的保证。若边带有收益、成本，或图含同部之间的边乃至奇环，就需要相应的带权或一般图匹配算法，不能只更改输入解释而沿用本算法的证明。

参考：[2]