问答题 193 /376

KM算法

参考答案

参考回答:

匈牙利算法：求最大匹配，那么我们希望每一个在左边的点都尽量找到右边的一个点和它匹配。我们依次枚举左边的点x的所有出边指向的点y，若y之前没有被匹配，那么(x,y)就是一对合法的匹配，我们将匹配数加一，否则我们试图给原来匹配y的x’重新找一个匹配，如果x’匹配成功，那么(x,y)就可以新增为一对合法的匹配。给x’寻找匹配的过程可以递归解决.

从一边的未饱和点出发，寻找增广路。复杂度：O(VE)

KM算法：给定一个带权的二分图，求权值最大的完备匹配

相等子图的完备匹配=原图的最大权匹配

1)初始化可行性顶标

2)对n个点在相等子图中寻找增广路

(1)初始化访问标记

(2)寻找增广路

(3)若增广路不存在，则修改交错路中的顶标，直到对某个点而言找到一条增广路为止

3)求得最大权

算法时间复杂度O(n3)O(n3)

纠错收藏

查看讨论