当您的图有多个组成部分时,如何找到最大二部匹配?每个组件都可以用两种方式着色。为了运行最大匹配例程,您如何确定两个集合X和Y?
发布于 2011-04-20 05:44:15
如果您的图有几个不同的连接组件,您可以通过在每个组件中找到最大匹配并返回它们的并集来查找图中的最大匹配。
至于如何确定集合X和Y,存在许多算法来检测特定图是否为二部图,如果是,则为节点分配标签以恢复这两个组。您可以使用修改后的DFS或BFS相当容易地做到这一点。因此,针对您的问题的算法可能是
中查找最大匹配
希望这能有所帮助!
发布于 2011-04-20 06:30:37
不要从边的角度来看匹配,而是将看作一组边。这一观点使我们更加清楚地认识到,无论您如何连接子结果,它在以后仍然是可以的。
发布于 2011-04-20 04:13:47
我不知道断开连接的图,但如果你有一个像我这样的完整图,你可能会感兴趣:http://wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html。它使用一种改进的Floyd-Warshall算法来寻找最大匹配。我不知道这和匈牙利算法有什么不同。
https://stackoverflow.com/questions/5716386
复制相似问题