匈牙利算法举例,匈牙利算法优缺点

匈牙利算法（Hungarian algorithm），其核心就是寻找增广路径，是一种用增广路径求二分图最大匹配的算法。

匈牙利算法是一种在P问题内（多项式时间内）求解任务分配问题的组合优化算法。它推动了后来的原始对偶方法。

匈牙利算法是美国数学家哈罗德·库恩于1955年提出的。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。

二分图（Bipartite graph）又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，A、B内部的点不相交，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i∈A, j∈B)，则称图G为一个二分图。

如图2-1左边图转换成一个二分图。

图2-1

一个图为二分图的充分必要条件是至少有两个点，并且如果存在回路的话，那么回路的长度(长度指的是该回路连接的点的数目)必须为偶数。

二分图的匹配：

给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

极大匹配是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。

最大匹配是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。匈牙利算法就是找出这样一个最大匹配的边数。对于图来说，最大匹配不是唯一的，但是最大匹配的大小是唯一的。

如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完美匹配。图2-2中图d就是二分图的一个完全匹配（同时也是最大匹配），但是最大匹配不总是完全匹配。

图2-2

图a，图b，图c，图d中任意两条边的连接的顶点都没有相同的(换句话说，n条边必须连接2 * n个不相同的顶点)。所以他们都是图G的匹配。

图2-3

红线部分代表匹配或完美匹配。

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边...形成的路径叫交替路。

增广路径：若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。

换一个说法，从一个未匹配点出发，走交替路，如果途径另一个未匹配点，则这条交替路称为增广路。如图2-4所示，红色结点代表匹配结点， 红色边代表匹配边，黑色边代表非匹配边。