Hopcroft 算法：二分图匹配的利器
Hopcroft 算法的核心在于快速找到最大匹配。它巧妙地利用了每次寻找“极大最短增广路集”的策略来减少匹配次数。如何高效地找到这个关键的“极大最短增广路集”呢？ 首先，利用类似匈牙利算法中的距离标号来扩展树，找到所有距离最短的未匹配点。然后，从每个找到的未匹配点出发，通过深度优先搜索（DFS）回溯到起点，并标记路径上的点，就能得到一条增广路。所有增广路的集合就构成了我们所需的“极大最短增广路集”。 整个寻找过程仅需 O(m) 的时间复杂度，其中 m 代表图中的边数。
文件大小：613.5KB
评论区