二部匹配

Question

如何用C或C++实现二部匹配算法(可能基于最大流算法)？

具体地说，我在一个文件中有这个输入：(1,3) (1,5) (2,5)

(M，F) -->其中M表示男性的id，F表示女性的id。

我需要找到匹配的最大数量，并显示匹配的情侣。喜欢:匹配: 1&3，2&5

我在一些书中读到过，我可以基于“网络中的最大流量”算法来解决这个问题，但除了“这个问题可以通过...算法解决”这句话之外，我找不到任何具体的信息。我对max-flow知之甚少，也不知道如何实现它……

Answer 1

是的，二部匹配可以简化为最大流量：

，，

1. ，你会得到一组节点，M和F。将M中节点m的有向边添加到F中的节点f (如果文件中有(m, f)对)。
2. 将来自S的具有有向边的单个节点S添加到<代码>D13(这是您的“超级源”节点)中的每个节点。<代码>H214<代码>H115将来自D17中每个节点的具有有向边的单个节点D16添加到D18(这是您的“超级接收器”节点)。现在，<代码>H219<代码>H120你需要找到从T.

到S的最大流(权重为1的所有边)

那么最大流量到底是什么呢？从S到T的流是一组边，对于每个节点( S和T除外)，其流内边的权重与流外边的权重相同。想象一下，您的图形是一系列管道，您正在向S的系统中倒水，并在T中将水排出。在这两个节点之间的每一个节点上，进入的水量必须与流出的水量相同。

试着说服自己，流对应于原始集合的匹配。(给定一个流，如何获得匹配？给定匹配，如何获得流？)

最后，为了找到图中的最大流，您可以使用Ford-Fulkerson algorithm。上面的wikipedia页面用伪代码对它进行了很好的描述。

Answer 2

是的，如果你已经有了解决最大流问题的代码，你可以用它来解决二部匹配问题，就像this讲座最后所示的那样，通过变换图来解决二部匹配问题，但如果你是从头开始的话，这可能不是正确的方法。如果您只想实现一些相当简单的代码来解决不太庞大的示例的问题，您最好使用简单的扩充路径方法，如here所述。这为您提供了一种O(|V||E|)方法，该方法非常容易编码，并且对于除非常大的图之外的所有图形都足够了。如果你想要更好的最坏情况下的性能，你可以尝试Hopcraft-Karp算法，它一次找到多个扩充路径，运行时间限制为O(sqrt(|V|)|E|)，但维基百科上的文章指出：

几位作者已经对二部匹配算法进行了实验比较。他们的结果总体上倾向于表明Hopcroft-Karp方法在实践中并不像在理论上那么好:它的表现优于更简单的广度优先和深度优先策略，以及推送重新标记技术。

在任何情况下，在尝试处理Hopcraft-Karp或维基百科文章参考中提到的推送相关技术之前，您都应该明确了解并能够实现简单的增强路径方法。

编辑:由于某些原因，上面的链接不能正确显示。下面是有问题的URL：(http://oucsace.cs.ohiou.edu/~razvan/courses/cs404/lecture21.pdf)、(http://www.maths.lse.ac.uk/Courses/MA314/matching.pdf)和(http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm)。

Answer 3

QuickGraph库包括一个二部匹配算法，我刚刚对其进行了研究，并对其进行了修复。它包装了Edmonds Karp最大流算法。

到目前为止，该算法的唯一文档是我添加的单元测试。如果任何人想要添加一个(希望更快)的实现，而不是简单地包装一个maxflow算法，请与我联系。