二分图检测（BFS/DFS） 题目描述 给定一个无向图，判断它是否是一个二分图。二分图是指能够将图中的所有顶点划分为两个不相交的子集，使得每条边的两个顶点分别属于这两个子集。换句话说，图中不存在奇数长度的环。 解题过程 二分图检测的核心思想是通过图着色（例如用两种颜色标记顶点），使得任意相邻顶点颜色不同。如果能够成功着色，则该图是二分图；否则不是。 步骤详解 初始化 创建一个颜色数组 color[] ，初始时所有顶点未着色（例如用 -1 表示）。 遍历图中的每个顶点，若当前顶点未着色，则从该顶点开始进行着色检查。 着色过程（以 BFS 为例） 从当前未着色的顶点 u 开始，将其着色为颜色 0，并加入队列。 当队列非空时，取出队首顶点 u ，遍历其所有邻居 v ： 若 v 未着色，则将其着色为与 u 相反的颜色（即 1 - color[u] ），并加入队列。 若 v 已着色且颜色与 u 相同，说明存在冲突，图不是二分图。 DFS 实现替代方案 递归遍历顶点 u ，对其邻居 v ： 若 v 未着色，递归调用 DFS 并传入相反颜色。 若 v 已着色且颜色与 u 相同，返回 false。 复杂度分析 时间复杂度和空间复杂度均为 O(V + E)，其中 V 是顶点数，E 是边数。 总结 通过系统性地对顶点进行着色，并检查相邻顶点颜色是否冲突，可以高效判断图的二分性。此算法在匹配问题、资源分配等场景有广泛应用。