二分图（Bipartite Graph）的判断与最大匹配 1. 二分图的概念 二分图 是一种特殊的无向图，其顶点集 \( V \) 可以被划分为两个互不相交的子集 \( U \) 和 \( V \)，使得图中的每条边都连接一个 \( U \) 中的顶点和一个 \( V \) 中的顶点。换句话说，二分图中不存在连接同一子集内顶点的边。 二分图通常用 \( G = (U, V, E) \) 表示，其中 \( E \) 是边集。 一个常见例子是“电影与演员”关系图：顶点集分为电影和演员两类，边表示某演员出演了某电影。 2. 二分图的判定 问题 ：给定一个无向图，判断它是否是二分图。 核心思想 ：二分图等价于 二着色图 ，即可以用两种颜色给所有顶点着色，使得任意一条边的两个端点颜色不同。如果图是连通的，这个过程可以通过深度优先搜索（DFS）或广度优先搜索（BFS）完成。 算法步骤 （以BFS为例）： 选择一个起始顶点，将其染成颜色0。 从该顶点开始BFS遍历： 对于当前顶点 \( u \)，检查其所有邻居 \( v \)。 如果邻居 \( v \) 未被染色，则将其染成与 \( u \) 不同的颜色，并将 \( v \) 加入队列。 如果邻居 \( v \) 已被染色，且颜色与 \( u \) 相同，则说明存在冲突，图不是二分图。 如果遍历完所有连通分量后未发现冲突，则该图是二分图。 时间复杂度 ：\( O(V + E) \)，其中 \( V \) 是顶点数，\( E \) 是边数。 3. 二分图的最大匹配 匹配 是指一组边，其中任意两条边没有公共顶点。 最大匹配 是指包含边数最多的匹配。二分图的最大匹配问题在现实中有广泛应用，如任务分配、婚配问题等。 匈牙利算法 是求解二分图最大匹配的经典算法。 算法步骤 ： 初始化：将所有边设为未匹配状态。 从左边集 \( U \) 的每个顶点出发，尝试寻找增广路径： 增广路径是指一条交替经过 未匹配边 和 已匹配边 的路径，且路径的起点和终点都是未匹配的顶点。 如果找到增广路径，则将路径上的边状态取反（未匹配变已匹配，已匹配变未匹配），这样匹配数会增加1。 重复步骤2，直到无法找到增广路径为止。此时得到的匹配就是最大匹配。 算法细节 ： 使用DFS或BFS搜索增广路径。 需要一个数组 match 记录右边集 \( V \) 中每个顶点当前匹配的左顶点（-1表示未匹配）。 在每次搜索中，需要标记已访问的顶点，避免重复搜索。 时间复杂度 ：\( O(V \times E) \)，但实际运行中常数较小，通常效率较高。 4. 算法示例 假设二分图如下： 左集 \( U = \{A, B, C\} \) 右集 \( V = \{1, 2, 3\} \) 边：\( A-1, A-2, B-1, B-3, C-2 \) 用匈牙利算法求最大匹配： 从A开始，匹配A-1。 从B开始，尝试匹配B-1，但1已被A匹配。于是回溯到A，看A能否换到2（找到增广路径B-1-A-2）。状态取反后：A匹配2，B匹配1。 从C开始，匹配C-2，但2已被A匹配。回溯到A，A无法换到其他边，因此C无法匹配。 最终最大匹配为{A-2, B-1}，大小为2。 5. 应用场景 任务分配：将工人与任务匹配，每个工人只能做一个任务。 推荐系统：用户与物品的关联。 社交网络分析：识别用户群体结构。 掌握二分图的判定和最大匹配算法，是图论中的基础技能，在面试中常与图遍历、搜索等结合考察。