我们知道在一般图中寻找最大匹配的标准算法。 https://en.wikipedia.org/wiki/Blossom_algorithm
我想了解的是，为什么需要单独处理开花？
我认为找到增广路径并对其进行补充就足够了。它也适用于奇数周期。
最佳答案
你是正确的，你可以使用以下通用算法形成最大匹配:
- 如果存在这样的路径，则沿着该路径增加匹配的大小。重复。
- 如果不存在这样的路径，你的匹配是最大的，你就完成了。
不过，挑战在于确定图中是否存在这样的增广路径。对于一个小图，找到一条路径可能并不难，但随着图变得越来越大，部分匹配的大小增加，它可能变得非常具有挑战性。在这种规模下，通过所有可能的路径进行蛮力搜索是不可行的。
在图是二分图(没有奇数长度的循环)的情况下，有一些基于广度优先或深度优先搜索修改的很好的算法可以做到这一点。它们工作得很好，因为您可以将节点分类为距起始节点的距离为奇数或偶数。对于奇数循环，这会崩溃，并且这些简单的算法不起作用。
blossom 算法存在的原因 - 以及 blossoms 首先存在的原因 - 是它们提供了一种机制，即使在存在 blossoms 的情况下也能有效地搜索图形以增加路径。直觉是，每次你看到一朵花，你都可以以一种不会影响你寻找增广路径的能力的方式将它缩小到一个点。收缩一个奇数循环会减小图的大小，并且通过递归，您将在很容易找到增广路径的地方结束图，或者您会发现没有增广路径。
所以在某种意义上，我们使用 blossoms 的原因是它使我们能够有效地(在多项式时间内)检查增广路径是否存在，如果存在，找到它们并在它们之间增广。
关于algorithm - 为什么我们在寻找最大匹配时需要处理开花？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55552274/