二分图又称作二部图，是图论中的一种特殊模型<br>设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图<br>给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。<br>选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)<br>如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。<br>
二分图匹配是图论中的一个重要概念，它在很多实际问题中有着广泛的应用，比如工作分配、资源调度等。二分图是由两个不相交的顶点集合构成，且每条边连接的是不同集合中的顶点。二分图匹配则是寻找在这样的图中，边的数目尽可能多但不使任何顶点被同一边连接的子图，即最大匹配问题。
最大匹配问题是寻找二分图中边数最多的匹配，其中没有两条边连接相同的顶点。这个问题的关键在于找到增广路径，这是一种特殊的路径，路径上的边交替属于当前匹配和未匹配的边。匈牙利算法是一种有效解决最大匹配问题的方法，由匈牙利数学家Edmonds在1965年提出。算法的基本思想是通过反复寻找并更新增广路径来增加匹配的大小，直到无法找到增广路径为止，此时得到的匹配即为最大匹配。
匈牙利算法的具体实现包括以下步骤：
1. 初始化一个空匹配。
2. 查找是否存在增广路径，如果找到则通过路径反转增加匹配数。
3. 重复步骤2，直到找不到增广路径。
在算法实现中，常用的数据结构如队列用于搜索路径，同时维护父节点数组以跟踪路径。算法的核心是深度优先搜索，通过回溯来找到增广路径，并更新匹配状态。
除了匈牙利算法，还有KM算法（Kuhn-Munkres算法，也称为Kuhn算法或匈牙利算法的扩展），它是解决带权重的完全二分图的最佳匹配问题。在带权重的二分图中，目标是找到权值总和最大的完备匹配，这对应于最大化整体效益的问题。KM算法通过迭代更新顶点的标号来逼近最优解，其时间复杂度为O(n^3)，在效率上优于简单的穷举方法。
二分图匹配问题不仅在理论上有重要的研究价值，而且在实际应用中也有很大的意义，例如在任务分配、网络路由、婚姻配对等领域都有其身影。通过理解这些算法，我们可以设计出更有效的解决方案，优化资源配置，提高系统效率。
