博主: Osilly
分类: 图论
一般图最大匹配
我们知道,二分图匹配有个著名的匈牙利算法(ntr算法 ),用于处理二分图的最大匹配关系.同样的,对于一般图,我们也有个常用的算法来处理一般图的匹配问题,这就是著名的带花树算法
一般图和二分图的区别
二分图是一个可以分为两个顶点集,并且这两个顶点集内部没有相互关系,只在一个集合和另一个集合之间存在关联
但一般图就是存在顶点集内部有关联的情况
二分图
一般图
这时候我们就不能用匈牙利算法,因为匈牙利算法便无法保证最优,这时带花树算法就基于匈牙利算法的基础上进行了处理环的情况
带花树算法
带花树算法下面几个博客讲的非常好,本文稍微补充一下算法过程中的一些细节方面
博客如下