二部图的快速最大匹配算法

Question

我试图解决下面的问题，但我的算法太慢。这是因为我使用Edmonds - Karp算法来寻找最大流，当应用于二分图时，也会给出最大匹配。它的运行时间是n^5，我想知道更快的算法来解决这个问题(特别是二分图)。我目前正在研究的一个算法是再贴到前线，它是n^3。

Answer 1

我用迪尼茨算法编写了二部匹配。还有一个定理，对于最大二部匹配问题类型的图，它具有与前面的关系标记相同的复杂性(而且更容易实现)。

在二分匹配问题求解过程中产生的网络中，相位的个数是由O(\sqrt{V})所限制的，从而导致了O(\sqrt{V} E)的时间限制。得到的算法也称为Hopcroft-Karp算法.更普遍地说，这个界限适用于任何单位网络--一个网络中，除源和接收器外，每个顶点都有一个输入边或容量边，或者是容量边，所有其他容量都是任意整数。

不幸的是，维基百科关于算法的文章还不足以实现它，我无法在网上找到更好的资源。我有我自己的实现，但我已经创建了它的指导，从别人在我的大学很久以前。

Answer 2

用于二分匹配的所谓匈牙利算法可以以较低的运行时复杂度实现.

Answer 3

Hopcroft-Karp算法为寻找Bipartite graph的最大匹配(或最小顶点覆盖)提供了最低的时间复杂度。

根据wikipidea，它运行在O(E * (V^0.5))中，E是总边，V是总顶点。在最坏的情况下(密集图)，这将是O(V^2.5)。