我正在尝试解决以下问题，但我的算法太慢了。那是因为我正在使用Edmonds - Karp 算法来找到最大流量，当应用于二分图时，它也能提供最大匹配。它的运行时间是n^5。我想知道任何更快的算法来解决这个问题（特别是二分图）。我目前正在研究的一种算法是Relabel to Front，即 n^3。
问问题
5973 次
3 回答
7
我使用dinitz's algorithm编写二分匹配。还有一个定理，对于最大二分匹配问题类型的图，它与重新标记到前面具有相同的复杂性（并且更容易实现）。
在解决二分匹配问题的过程中出现的网络中，阶段数以 O(\sqrt{V}) 为界，因此导致 O(\sqrt{V} E) 时间界限。由此产生的算法也称为 Hopcroft–Karp 算法。更一般地说，这个界限适用于任何单位网络——一个网络中的每个顶点，除了源和汇，要么有一个容量为 1 的单个进入边，或者有一个容量为 1 的单个出边，并且所有其他容量都是任意整数.
不幸的是，关于算法的维基百科文章不足以实现它，我在网上找不到任何更好的资源。我有自己的实现，但很久以前我在大学其他人的指导下创建了它。
于 2014-04-14T12:24:40.493 回答
2
用于二分匹配的所谓匈牙利算法可以以较低的运行时复杂度实现。
于 2014-04-14T12:14:34.240 回答
1
Hopcroft–Karp 算法为寻找最大匹配（或最小顶点覆盖）提供了最低的时间复杂度Bipartite graph。
根据维基百科，它在 中运行O(E * (V^0.5))，E是总边，V是总顶点。在最坏的情况下（密集图），这将是O(V^2.5).
于 2020-02-26T20:40:59.117 回答