匈牙利算法（Hungarian Algorithm）是一个用于解决二分图最大权匹配问题的经典算法，由匈牙利数学家Harold Kuhn与Egervary Jenő在1955年发明。它不但运行速度较快，而且理论上非常完美，是一种解决二分图匹配问题的最佳算法。
匈牙利算法有着自己独特的特点，可以解决二分图（Bipartite Graph）的最佳完美匹配问题，在计算机视觉，生物信息学等领域都有广泛应用。通过应用最大流与二分图理论可得到此算法，它的基本思想是通过每个已匹配点尝试寻找更合适的邻接点，形成增广路径并修改当前的匹配状态，最终使得匹配数最大。
匈牙利算法的核心在于寻找增广路径，而在寻找增广路径的过程中还用到了DFS搜索，因此它不仅是一种贪心算法，也具有一定的深度优先搜索思想。
匈牙利算法：图形最优匹配算法
匈牙利算法，也称Kuhn-Munkres算法，是图形最优匹配的经典算法之一。它是匈牙利数学家D. K?nig于1913年发明的，后经美国数学家Harold W. Kuhn和匈牙利数学家J. Munkres独立发扬光大，因此得名匈牙利算法。它被广泛应用于图形匹配、网络流、聚类分析、机器学习等领域。
所谓图形最优匹配，是指给定的两个集合A和B，它们之间有一定的关系（如相似度、距离等），我们的目标是在A和B之间找到一种最优的匹配方式，使得匹配度最大。匈牙利算法就是求解这个最优匹配的问题。
匈牙利算法的主要思想是通过二分图的最大匹配来得到原图的最大权匹配，以求得最优匹配结果。该算法的时间复杂度是O(n^3)。
匈牙利算法的基本步骤如下：
- 将原图分解成二分图（左部和右部）
- 构造与原图等价的二分图，左部的节点对应于原图的行，右部的节点对应于原图的列
- 对每个节点，计算其相邻节点的权值，如果该权值大于等于其它任一节点与它相连的边的权值，则选择该节点与其相邻节点匹配
- 不断更新未匹配节点的权值，直到所有节点都匹配为止
匈牙利算法虽然存在一定的局限性，但是其优秀的性能和良好的适用性，使它成为了图形匹配、网络流计算等领域的热门算法。
匈牙利算法及其应用
匈牙利算法又称为增广路算法，是解决二分图最大匹配问题的经典算法。这个问题可以抽象成一张二分图，一个点集代表左边的节点，另一个点集代表右边的节点。每个左边的节点都能与右边的节点进行匹配，但一般只存在部分可匹配的情况，即左边的节点只能与右边的节点配对，右边的节点也只有一次配对的机会。
匈牙利算法的具体实现是在二分图上操作的。可以用一个bool矩阵表示一个加权的二分图，其中true表示左边的节点与右边某个节点可以配对。接着从左边的每个节点开始，如果该节点尚未被匹配，则尝试将它指派给一个右边的未配对节点。如果该节点无法被匹配，则尝试从其他未被匹配的左边节点中寻找一个节点，并递归地执行上述尝试过程。
除了用于最大匹配的问题，匈牙利算法还可以解决其他一些问题。比如，在计算机视觉中，可以使用匈牙利算法进行对象跟踪，将每个对象与前一帧中的特定对象进行匹配。
