匈牙利算法详解：二分图最大匹配

"匈牙利法求解二分图最大匹配" 二分图是一种特殊的图，其节点可以被分成两个不相交的集合，使得每条边都连接集合内的不同节点。在二分图中，最大匹配问题是寻找尽可能多的、不相交的边集合，使得每个节点最多被一条边覆盖。这个问题在很多领域都有应用，例如优化调度、网络设计、分配问题等。 匈牙利算法，也称为Kuhn-Munkres算法或KM算法，是解决二分图最大匹配问题的一种高效算法。它的核心思想与最大流算法相似，但针对二分图的特性进行了优化，简化了网络构建，无需额外的源点和汇点。在匈牙利算法中，主要操作是寻找并利用增广路径来逐步增加匹配的数量。 增广路径是匈牙利算法的关键概念，它满足以下特征： 1. 奇数条边：增广路径包含奇数条边，因为这样可以通过调整匹配来增加匹配数。 2. 起点和终点：路径的起点在二分图的左半边，终点在右半边，确保了路径能有效地在匹配中增加新的连接。 3. 交替出现：路径上的节点交替位于左右两部分，反映了二分图的性质。 4. 无重复点：路径上的每个点都是唯一的，避免了循环。 5. 配对状态：起点和终点是未配对的节点，路径上的其他点已配对。 6. 边的匹配性：奇数位置的边不在原始匹配中，偶数位置的边在原始匹配中。 7. 增广操作：通过改变增广路径上的边，可以增加匹配数。具体来说，将奇数位置的边添加到匹配中，同时移除偶数位置的边。 匈牙利算法的执行过程大致如下： 1. 初始化匹配，通常是随机或空匹配。 2. 寻找增广路径，如果找到，则进行增广操作更新匹配。 3. 重复步骤2，直到无法找到增广路径为止，此时达到最大匹配。 匈牙利算法的优点在于它保证了找到的是二分图的最大匹配，且时间复杂度相对较低，通常为O(n^3)，其中n是图中的节点数。在实际应用中，尤其是在ACM（国际大学生程序设计竞赛）等算法竞赛中，匈牙利法因其简洁和高效，成为解决二分图匹配问题的首选方法。