UD5工具箱
这是为您生成的一个二分图最大匹配 Hopcroft-Karp 算法的交互演示工具，您可以直接在页面上调整图结构并逐步观察算法执行过程。
```html
二分图最大匹配 · Hopcroft-Karp 算法演示
交互式可视化 | 逐步演示 BFS 分层与 DFS 增广过程
图设置
算法控制
步骤 0/0
0.7s
当前步骤
点击"运行 Hopcroft-Karp"开始算法演示。
图例
左部节点
右部节点
普通边
匹配边
增广路径
BFS当前层
邻接矩阵（点击切换边）
行=左部节点 L，列=右部节点 R
点击单元格添加/删除边 | 蓝色=有边 | 白色=无边
常见问题与知识点
什么是二分图（Bipartite Graph）？
二分图是一种特殊的图，其顶点可以分为两个不相交的集合（左部U和右部V），使得每条边都连接一个左部顶点和一个右部顶点。同一集合内的顶点之间没有边。二分图在匹配问题、任务分配、推荐系统等领域有广泛应用。
什么是最大匹配？
匹配是图中一组边的集合，其中任意两条边不共享顶点。最大匹配就是包含边数最多的匹配。在二分图中，最大匹配可以解决诸如"最多能为多少人分配工作"、"最多能撮合多少对"等问题。如果匹配覆盖了所有左部（或右部）节点，则称为完美匹配。
Hopcroft-Karp 算法的核心思想是什么？
Hopcroft-Karp算法通过多轮迭代来寻找最大匹配，每轮分为两个阶段：
① BFS阶段：从所有未匹配的左部节点出发，交替经过未匹配边和匹配边，构建层次图（layered graph），计算每个左部节点到最近未匹配右部节点的最短距离。
② DFS阶段：沿层次图寻找多条顶点不相交的增广路径，一次性更新匹配。
每轮可以找到多条增广路径，从而将时间复杂度优化到 O(√V · E)。
① BFS阶段：从所有未匹配的左部节点出发，交替经过未匹配边和匹配边，构建层次图（layered graph），计算每个左部节点到最近未匹配右部节点的最短距离。
② DFS阶段：沿层次图寻找多条顶点不相交的增广路径，一次性更新匹配。
每轮可以找到多条增广路径，从而将时间复杂度优化到 O(√V · E)。
Hopcroft-Karp 与匈牙利算法有什么区别？
匈牙利算法（Kuhn-Munkres的简化版）每次只寻找一条增广路径，时间复杂度为O(V·E)。Hopcroft-Karp算法每轮寻找多条增广路径，时间复杂度为O(√V·E)，在稠密图上显著更快。对于大规模二分图（如推荐系统中的用户-物品匹配），Hopcroft-Karp是更优的选择。
什么是增广路径（Augmenting Path）？
增广路径是一条交替路径：起点是未匹配的左部节点，终点是未匹配的右部节点，路径上的边交替属于"未匹配边"和"匹配边"。对增广路径进行"翻转"（将未匹配边变为匹配边，匹配边变为未匹配边），匹配数就会增加1。这是所有匹配算法的核心操作。
Hopcroft-Karp 算法的时间复杂度是多少？
Hopcroft-Karp算法的时间复杂度为O(√V · E)，其中V是顶点数，E是边数。这是目前二分图最大匹配问题的最优已知时间复杂度之一。之所以是√V，是因为BFS阶段最多执行2√V轮（因为每轮后最短增广路径长度至少增加2）。
这个算法有哪些实际应用？
应用非常广泛，包括：
• 任务分配：将工人分配到最适合的工作岗位
• 在线约会/匹配：用户之间的偏好匹配
• 网络流量调度：交换机端口匹配
• 图像特征匹配：计算机视觉中的特征点对应
• 推荐系统：用户与内容的精准匹配
• 课程安排：学生选课与教室分配
• 任务分配：将工人分配到最适合的工作岗位
• 在线约会/匹配：用户之间的偏好匹配
• 网络流量调度：交换机端口匹配
• 图像特征匹配：计算机视觉中的特征点对应
• 推荐系统：用户与内容的精准匹配
• 课程安排：学生选课与教室分配
BFS阶段中的"层次"是什么意思？
BFS构建的层次图（layered graph）为每个左部节点分配一个距离值
dist[u]，表示从该节点出发、沿交替路径到达某个未匹配右部节点的最短距离。DFS阶段只沿着dist严格递增的路径搜索，这确保了找到的增广路径都是最短的，并且多条路径之间不会相互干扰。