algorithm - 断开图中的最大二分匹配

Question

当你的图有多个组件时，你如何找到最大的二分匹配？每个组件可以用两种方式着色。您如何确定两组 X 和 Y 以运行最大匹配例程？

Answer 1

不要从边缘的角度看匹配，看是作为一组边缘。这种观点更清楚地表明，无论您如何加入子结果，后面仍然可以。

1. 将您的图表分成连接的组件

2. 使用您选择的算法为每个图形组件找到最大匹配。

3. 找到的匹配的并集是整个图的最大匹配。

Answer 2

如果您的图表有几个不同的连通组件，您可以通过在每个组件中找到最大匹配并返回它们的并集来找到图中的最大匹配。

至于如何确定集合 X 和 Y，存在许多算法来检测特定图是否为二分图，如果是，则为节点分配标签以恢复这两个组。您可以使用修改后的 DFS 或 BFS 相当轻松地做到这一点。因此，您的问题的算法可能是

1. 在整个图形上运行 DFS 以将其分解为连接的组件。
2. 对于这些组件中的每一个：
   1. 在这些组件上运行 DFS 以恢复组 X 和 Y 中的节点。
   2. 使用最大二分匹配算法在该组件中找到最大匹配。
3. 将所有结果组合在一起以获得总体答案。

希望这可以帮助！

Answer 3

我不知道断开连接的图表，但如果你有一个像我这样的完整图表，这对你来说可能很有趣：http ://wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html 。它使用修改后的 Floyd-Warshall 算法来找到最大匹配。我不知道这与匈牙利算法之间的区别。