匈牙利算法 >> NoAlGo博客

匈牙利算法 » NoAlGo博客

匈牙利算法是解决二分图最大匹配的经典算法，由匈牙利数学家Edmonds提出，核心是通过寻找增广路径以求得最大匹配。
本文将介绍匈牙利算法的思想及原理解释，最后提供一个C++代码实现。

算法原理

无向图G=(V, E)中，如果顶点V可以分成不相交的子集(X, Y)，使得图中每一条边所关联的两个顶点分别属于两个不同的顶点集，称G为一个二分图（二部图或偶图）。

给定二分图G，如果G的一个子图中M，M中任意两条边都不依附于同一个顶点（不相邻），则称M为一个匹配。
所有匹配中边数最大的称为最大匹配。
如果原图的所有顶点都和M中的某条边关联，称M为完备匹配，也称完美、完全匹配。

Note：
图G=(V,E)的子图是指图G1=(V1,E1)，其中V1⊆V，E1⊆E。
图G=(V,E)的生成子图是指图G2=(V2,E2),其中V2=V，E2⊆E。
生成子图的顶点一定跟原图一样，而子图可以不一样。

给定一个二分图G，怎么求其最大匹配？这就是匈牙利算法解决的问题。
从一个未匹配顶点出发，交替经过非匹配边和匹配边的路径，称为交错路。
起点和终点都是未匹配顶点的交错路称为增广路。

Read full article from 匈牙利算法 » NoAlGo博客