扩展路径算法-最大匹配
我正在阅读扩充路径或Kuhn的算法，以便在未加权的二部图中找到最大匹配大小。
该算法试图找到一条交替的路径(由交替的未匹配和匹配的边组成)，在未匹配的顶点开始和结束。如果找到备用路径，则增加该路径，并将匹配计数加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;
} 这样，在迭代过程中不匹配的左侧顶点将永远不会再次尝试。我不明白为什么这是最优的？
回答 2
Stack Overflow用户
发布于 2016-12-08 15:49:44
这足以证明算法结束后不会留下任何扩充路径。因为没有增加路径意味着最大流量。假设Ai是左边的i个顶点，Bi是右边的i个顶点。
如果Ai已经匹配，那么它将在任何扩充路径中保持匹配。
所以，我们唯一关心的是，当我们考虑了Ai，没有发现匹配，但在for循环中进行了一些迭代后，Ai突然有了新的增强路径。我们将证明这永远不会发生。
让我们考虑Ai之前没有增广路径，假设S是dfs(i)可以访问的顶点集。只有两种方法可以让新顶点(以前不在S中)在之后包含在S中。
- 对于S中的某些Ax，边Ax - By从匹配更改为不匹配(之后将包含在S中)
矛盾。因为我们应该通过- Ax - ... - Sink找到扩充路径，但是Sink不在S中，所以我们不能这样做。
- 对于S中的某些By，边By - Ax从不匹配更改为匹配(之后Ax将包含在S中)
又是矛盾。这一次，我们应该找到扩展路径Ax - By - ... - Sink，但同样，我们无法到达Sink from By。
由于上述原因，不可能意外地向左增加意味着最大流量的路径。
Stack Overflow用户
发布于 2016-08-13 02:59:50
根据我的理解，该算法试图为每个左侧顶点u(从0到n1-1)找到一条增广路径。如果存在这样的路径，则可以将u添加到匹配中，使之前添加的所有顶点都保持在匹配中。如果不存在这样的路径，则不可能将u添加到匹配中。这源于扩充路径的特殊属性。
当我们为每个u检查这一点时，我们找到了可能添加到匹配中的最大顶点数，从而导致了最优性保证。
https://stackoverflow.com/questions/25519832
复制
相似问题
Pebble - Detect Shake手势
Swift - Shake手势关闭子视图控制器
滑动手势取消IBAction的触发分段
将变量从手势识别器函数传递给IBAction
配置抽头手势识别器，以响应在点击位置的ibaction
领取专属 10元无门槛券
AI混元助手 在线答疑
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
