匈牙利算法与KM算法的区别

前记

在学习过程中，发现很多博客将匈牙利算法和KM算法混为一谈，当时只管用不管分析区别，所以现在来分析一下两个算法之间的区别。

匈牙利算法在二分图匹配的求解过程中共两个原则：

1.最大匹配数原则
2.先到先得原则

而KM算法求解的问题则是在匈牙利算法上的延伸——也就是在最大匹配的情况下保证边权和最小。

详细的说：

匈牙利算法解决的二分图类似下面这种：

而KM算法解决的当是下面这种：

当然这不代表KM算法不可以解决匈牙利问题。

虽然解决的问题相似，但匈牙利算法和KM算法的实现方式截然不同，不过KM算法的博客就先咕了（（

小结

上面的内容讲解了匈牙利算法与KM算法在解决的问题上的区别。

整体来说，匈牙利算法在求解过程中在 最大匹配原则 的基础上遵循 先到先得原则，
KM算法在求解过程中则在 最大匹配原则 的基础上先保证 全局最小代价，在全局代价最小的情况下遵循 先到先得原则 分配最终结果。希望能通过一篇分析明白匈牙利算法和KM算法有一定的区分。最后，如果文章有误，欢迎 @Tonvia