我正在阅读扩充路径或库恩算法，以找到未加权二分图中的最大匹配大小。
该算法试图找到一条从不匹配顶点开始和结束的交替路径（由交替的不匹配和匹配边组成）。如果找到一条交替路径，则该路径将被扩充，匹配计数将增加1。
我能理解这个算法，但我在理解它的一般实现方式方面有问题。以下是一个参考实现—https://sites.google.com/site/indy256/algo/kuhn_matching2。
在每个阶段，我们都应该尝试从左边一个不匹配的顶点开始找到一条交替的路径。然而，在给定的实现中，在每次迭代中，我们不是尝试将所有不匹配的顶点作为可能的起始位置，而是仅从单个不匹配顶点开始搜索，如以下代码所示-
for (int u = 0; u < n1; u++) {
if (findPath(graph, u, matching, new boolean[n1]))
++matches;
}
这样，左边的顶点在迭代过程中不匹配，就不会再尝试了。我不明白为什么这是最优的？
这足以证明算法结束后不会留下任何扩充路径。因为没有增加路径意味着最大流量。假设A[i]是第i个左边的顶点，B[i]是第一个右边的顶点。
如果A[i]已经匹配，那么它将在任何增强路径中保持匹配。
所以，我们唯一关心的是，当我们考虑了A[i]，但没有找到匹配项，但在for循环中进行了一些迭代后，A[i]突然有了新的扩充路径。我们会证明这永远不会发生。
让我们考虑A[i]之前没有扩充路径，并假设s是dfs（i）可以访问的顶点集。只有两种方法可以使新顶点（以前不在S中）在之后包含在S中。
-
对于S中的一些A[x]，边缘A[x]-B[y]从匹配变为不匹配（之后B[y]将包含在S中）
矛盾。因为我们应该找到扩充路径B[y]-A[x]-…-Sink，但Sink不在S，所以我们不能那样做。
-
对于S中的一些B[y]，边缘B[y]-A[x]从不匹配变为匹配（之后A[x]将包含在S中）
矛盾再次出现。这一次，我们应该找到扩充路径A[x]-B[y]-…-Sink，但再说一遍，我们无法从B[y]到达Sink。
由于上述原因，不可能意外地留下意味着最大流量的增大路径。
根据我的理解，该算法试图为每个左顶点u（从0到n1-1）找到一条扩充路径。如果存在这样的路径，则可以将u添加到匹配中，从而在匹配中保留所有先前添加的顶点。如果不存在这样的路径，就不可能将u添加到匹配中。这源于扩充路径的特殊性质。
当我们对每个u进行检查时，我们发现可以添加到匹配中的最大顶点数量，从而得到最优性保证。