判别两棵树是否相等 设计算法_从匈牙利算法到KM算法

网上搜了好多KM算法的文章，都写得云里雾里。看了半天之后，我终于看懂了。其实KM算法非常简单，只要会匈牙利算法了，一下就能看懂KM算法。

如果大家对自己的匈牙利算法不够自信的话，可以先复习一下，放上我的上一篇文章。

https://zhuanlan.zhihu.com/p/208596378​zhuanlan.zhihu.com

KM算法是解决什么问题的?

要知道，最大匹配不是唯一的，不同的人用匈牙利算法，可能找到不同的匹配结果。那么怎么评估这些不同的匹配呢？还是拿情侣配对举例子，一种评价方法就是，看情侣彼此的满意程度。比如，有的人当媒人，介绍的每一对情侣都极其满意，有的人当媒人，虽然把情侣都凑在了一起，介绍的每一对情侣只是略微有意向，但是没和最喜欢的在一起。

这个喜欢程度，就是给原本的二分图，加了一个权重。

图1 权重二分图的最大匹配问题

在权重的前提下，该如何寻找最大匹配，且使得权重最大呢？KM算法就是为了解决这个问题的。

权重问题的转化 / KM算法和匈牙利算法的关系

我刚开始学习的时候，根本没有想明白，KM算法和匈牙利算法的关系。

遇到不会的问题，一个思路就是想办法转换成自己会的问题。我们现在知道匈牙利算法能解决最大匹配的问题，现在加了权重，KM算法实际上就是想了个办法，将问题转换成了匈牙利算法可以解决的形式。

现在二分图带了权重，可以理解为加了一种约束，这种约束让我们优先选择那些权重大的边出来，进行匹配。

因此我们要先把权重最大的边都挑出来，学术一点，就是挑一个子图出来。因为我们挑出来的都是权重最大的边，我们只要在这个子图中，找到最大匹配，这个最大匹配一定是权重最大的（很重要，意思就是这个子图里，在上面随便找都是权重最大的匹配，这样我们就能用匈牙利算法解决问题了）。流程就是：

找权重最大的边组成的子图--------→在这个子图上找最大匹配

上述流程很简单吧，有一个问题是，我们都找最大权重的边组成子图，这个子图很小，很容易冲突。形象来说，大家找对象的要求都太高了，很可能会没法满足他们的要求。众所周知，找不到对象是很惨的，因此对象还是得找的。这时候只能委屈一部分人，让他稍微降低一下的要求，让他从别的人里挑对象。

因此目前的流程变成了：

-----------

这个KM算法的流程，核心思想就是：优先选择最满意的，因为要求太高找不到对象的那些人，降低标准扩大择偶范围，直到找到对象为止。

这个问题中，找最大匹配的那一部分我们会了呀，用匈牙利算法就搞定了。剩下就是两个问题了：

（1）怎么找到这个所谓的“权重最大的子图”。

（2）怎么扩大择偶范围。既不能降得太低，也不能不降。

上述两个问题，就是KM算法的精髓。

这个权重最大的子图，就是“相等子图”。扩大择偶范围，就是“顶标的更新---建立新的相等子图”的过程。

要注意的是，上面说的权重最大，并不是整个图的范围内权重越大越好，而是目前能力范围内我们能选的最大的权重边（毕竟有些人需要降低标准才能找到对象）。

接下来就要讲如何解决上面提出的两个问题。

第一个问题 如何寻找“权重最大的”子图？

首先强调一点，我们的这个子图的目的，是为了实现一个效果：

在这个子图上，不考虑权重找到最大匹配 等价于 在带权重的图上找权重最大的最大匹配。

我们挑一伙人出来，这些人彼此的满意度都比较高，那些低的暂时不考虑。在这伙人里找对象。找不到了再考虑加人进来。

为了实现这个目标，我们给每个人，增加一个顶标。我们暂不考虑这个顶标是怎么加的，将在下一步中再详细讲这个问题。现在假设我们已经有一个顶标了。

这个顶标是我们决定一条边是否加入子图的依据。顶标可以理解为择偶的最高标准，如果双方的适配程度达到了这个最高标准，就加入到择偶范围内来，就是加入到子图中。

因此，比如说小王择偶的最高标准是

，小李择偶最高标准。小王和小李的喜欢程度是 （即二分图中，小王和小李的连线权重），若

,

小王和小李的连线就加入子图中，进入择偶候选人范围。注意到上面这个等式，于是这样选出来的子图，叫做相等子图。

然而这个最高标准，是不断变化的。也就是下一个问题，如何不断地调整最高标准，让择偶范围不断变化。

第二个问题 如何扩大择偶范围？

我们这里拿一个具体的例子来看。

这里有5个女生x1-x5， 5个男生y1-y5。他们之间为0就是没有连线，大于0的数是权重，就是他们相互喜欢的程度。

第一步，最高标准初始化。

需要注意的是，我们是一个无向的二分图，意思就是权重是双方共同的喜欢程度，因此可以选一个人作为代表就行了。于是，我们让女生做单方面的选择。

于是男生们的顶标都设为0。

一开始女生们都想找最喜欢的对象，我们将她们的最高标准都设为她们最喜欢的那个。比如，x1对所有男生都有意向，喜欢程度分别是3,5,5,4,1。那小王目前的最高标准就是5。

在第一次选择中，y2、y3加入择偶范围，其他三人暂不考虑。所有女生都这样，选出自己最喜欢的加入择偶范围。

我们就得到了子图

这样的好处就是，这样挑出来的子图中，彼此喜欢程度一定是最大的。这样我们就不用考虑权重的问题了，问题就变成了一个在局部子图上，挑选最大匹配的问题，就可以用匈牙利算法解决了。

接下来，我们就用匈牙利算法来给她们分配对象。红线表示匹配好了。

x1和x2都成功找到了对象。但是x3也愿意和y2一起。冲突了。一开始有了矛盾，我们先用匈牙利算法给她们尝试解决一下。

我们找到一条增广路，x3---y2---x1----y3。取个反，冲突就解决了。x3也找到了自己最满意的对象。

轮到x4了。x4最满意的是y2和y3，但是都被挑走了。我们先用匈牙利算法，给她也试一下。开始找增广路。x4----y2----x3----y3------x1----y2----????，发现到了y2，找不下去了，又回到y3了。 我们优先广度，试试另一条路。 x4----y3-----x1------y2-----x3------y3----???，发现又找不下去了。

此时此刻，匈牙利算法也解决不了了，就要开始扩大择偶范围了。

第二步，最高标准调整。

我们随便选择一条上面没走下去的交替路（由于没有成功找到另一个未匹配的对象，所以这条交替路没有资格被称为增广路）比如就选这条：

x4----y2----x3----y3------x1----y2----????

这条路线，在很多文章里也会被成为交替树。一旦找到增广路，我们就能扩大匹配范围，给x4也找到对象。但是现在失败了，这个失败的本质是和路线上的人发生了冲突。2

于是我们看看，有哪些人和x4的失败有关。女生：x1，x3，x4。男生：y2，y3。

现在我们要协调这几个人的择偶最高标准（也就是他们的顶标），扩大择偶范围了。

首先，我们不能破坏原有的关系，原来的顶标都是设计好的，能保证选到自己最喜欢的对象。所以要保证他们之间最高标准不变，这样保证原来的匹配不会发生变化。

这里让上面和x4冲突的这些人里：女生的顶标减少，男生顶标增加，这样他俩合起来标准不变。

但是，女生的顶标减小了，其他人的机会就来了。

再回到刚刚我们挑子图的公式，就是小王配小李的这个等式，

,

现在小王因为和别人冲突了，降低了标准，W就减小了，也就是有些权重没那么大的边，现在有机会被加进子图里了。

现在女生：x1，x3，x4都喜欢y2和y3，发生冲突了，而y1,y4,y5还没被他们考虑。原本x1的标准是5，现在她要考虑y1的话，x1y1权重是3，需要降低2个标准。

同理，x1y4需要降低1； x3y1需要降低2， x3y4需要降低4-1=3；x3y5需要降低4-0=4。x4也一样算法。

所以考虑到最大权重，最少要降低1个标准。

因此我们把x1，x3，x4的标准-1，y2，y3对应+1。

在这个标准下，我们依旧要挑满足“两人顶标和=两人连线权重”的边。

可以看出来，x4同学降低标准后，所有男同学都满足她的标准了。

这时候按照匈牙利算法，x4和y1配对，冲突了，找到增广路x4---y1---x2---y4。取反后，x4和y1配对，x2和y4配对。

再给x5找对象。x5也找到了y5作为对象。

现在所有人都有对象了。

此时他们的权重为4+2+3+0+3+0+1+1 +0+0 =14。

总结

以上是生活随笔为你收集整理的判别两棵树是否相等 设计算法_从匈牙利算法到KM算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。