匈牙利算法与KM：解决最大匹配问题

"匈牙利算法与KM.ppt" 在图论中，匈牙利算法是一种高效解决二分图最大匹配问题的方法。二分图，又称作二部图，是指一个无向图的顶点集可以被分成两个互不相交的子集，使得每条边的两端分别属于这两个不同的子集。这种结构在很多实际问题中都有应用，例如在任务分配、资源调度以及网络设计等场景。 最大匹配是二分图的核心概念，它指的是在一个二分图中找到一个子集，其中没有两条边连接相同的顶点，同时这个子集的边数尽可能多。如果图中的每个顶点都能与一条边关联，那么这个匹配就是完全匹配或完备匹配，它是最大匹配的一种特殊情况。 匈牙利算法，也称为Kuhn-Munkres算法或KM算法，是由John Kuhn和James Munkres分别独立提出的。它的核心思想是利用增广路径来不断改进匹配状态，直到找不到增广路径为止。增广路径是一个特殊的路径，其路径上的边按照匹配和未匹配的状态交替出现，起点和终点都是未匹配的顶点。增广路径的存在意味着当前匹配不是最大匹配，通过对增广路径进行操作，可以找到一个更大的匹配。 匈牙利算法的具体步骤如下： 1. 初始化：创建一个空匹配M。 2. 查找增广路径：如果存在增广路径P，通过改变P上的匹配状态（即将匹配的边变为未匹配，未匹配的边变为匹配），可以得到一个新的匹配M'，使得M'的匹配数比M多。 3. 重复步骤2，直到找不到增广路径为止，此时的匹配M就是最大匹配。 在程序实现中，通常采用DFS或BFS搜索增广路径，这里给出的代码片段展示了DFS的思路，通过队列（queue）存储搜索过程中的节点，并使用father数组记录父节点信息。在遍历过程中，寻找未匹配且有连接的节点，若找到增广路径，更新匹配状态。 匈牙利算法的时间复杂度是O(n^3)，其中n是图中顶点的数量，这使得它在处理大规模问题时仍然具有较高的效率。KM算法不仅限于二分图，还可以扩展到解决赋权匹配问题，即每条边都有一个权重，目标是最小化所有匹配边的权重之和。 总结来说，匈牙利算法是解决二分图最大匹配问题的重要工具，通过增广路径的迭代搜索，可以高效地找到最优解。在实际应用中，如作业调度、网络路由优化、市场匹配等领域，都有广泛的应用。