匈牙利算法实现最大二分图匹配

"最大二分图分配" 在计算机科学中，最大二分图分配问题是一个经典图论问题，它涉及到寻找一个二分图的最大匹配。二分图是一种特殊的图，其节点可以分为两个不相交的集合，其中任何两个属于同一集合的节点之间都没有边相连。最大二分图匹配的目标是在这两个集合之间找到尽可能多的独立边，即每条边连接不同集合中的一个节点。 这段代码提供了两种实现最大二分图匹配的方法：一种是基于广度优先搜索（BFS）的匈牙利算法，另一种是深度优先搜索（DFS）的实现。这两种方法都用于确定两个顶点集合间最大数量的互不冲突的边。 匈牙利算法，也称为Kuhn-Munkres算法，是一种高效的解决最大匹配问题的方法。算法的核心思想是通过逐步增加匹配来寻找最大匹配，每次尝试将未匹配的节点与未扫描的节点配对，直到无法找到新的配对为止。在这个过程中，使用标记和扫描的概念来追踪可能的匹配路径，确保所有节点都被考虑且不违反匹配规则。 代码中，`main()` 函数首先读取输入，初始化数据结构，然后应用匈牙利算法进行匹配。`dfs()` 函数则是DFS版本的实现，通过遍历图的邻接矩阵，搜索可能的匹配路径，并更新匹配状态。 在BFS实现中，`map[][]` 存储了节点之间的连接关系，`match1[]` 和 `match2[]` 用于记录匹配结果，`prev[]` 记录回溯路径。在DFS实现中，`searched[]` 标记已搜索过的节点，`prev[]` 保存前驱节点信息。 两种算法的运行结果都是输出匹配的数量，如果是两个集合的节点都能成功匹配，则输出"YES"，否则输出"NO"。在DFS实现中，`num` 计算最终的匹配数，并在循环结束后打印。 在实际的人工智能应用中，最大二分图匹配问题可以应用于各种场景，如任务分配、资源调度、社交网络分析等，寻找最优的配对策略以提高效率或满足特定条件。这两种算法虽然都是解决同一问题，但在复杂性和效率方面可能存在差异，适用于不同的问题规模和性能要求。