二分图检测（BFS/DFS） 题目描述 给定一个无向图，判断它是否是二分图。二分图是指可以将图中的所有顶点分成两个不相交的集合，使得同一集合内的顶点之间没有边相连。换句话说，图中不存在长度为奇数的环。 解题过程 核心思路 二分图的判定等价于图的二着色问题：尝试用两种颜色（如0和1）对顶点染色，使得相邻顶点颜色不同。若染色成功，则为二分图；若在染色过程中发现相邻顶点颜色相同，则不是二分图。 算法选择 使用BFS或DFS遍历图，在遍历过程中对顶点进行染色。以下以BFS为例详细说明步骤。 具体步骤 初始化 ：创建颜色数组 color[] ，初始值为-1（表示未染色）。 遍历每个连通分量 ：因图可能不连通，需检查每个未访问的顶点。 BFS染色过程 ： 从当前顶点 u 开始，将其染为颜色0，并入队。 当队列非空时，取出队首顶点 u ，遍历其所有邻居 v ： 若 v 未染色（ color[v] == -1 ），将其染为与 u 相反的颜色（ color[v] = 1 - color[u] ），并入队。 若 v 已染色且颜色与 u 相同，说明冲突，立即返回 false 。 结果 ：若所有连通分量均染色成功，返回 true 。 示例演示 假设图有顶点0、1、2、3，边为(0,1)、(1,2)、(2,3)、(3,0)： 从顶点0开始染色： color[0]=0 ，邻居1染为1。 顶点1的邻居2染为0，顶点2的邻居3染为1。 顶点3的邻居0已染色且颜色为0，与3的颜色1不同，无冲突。 染色成功，图为二分图（可划分为集合{0,2}和{1,3}）。 复杂度分析 时间复杂度：O(V+E)，其中V为顶点数，E为边数。 空间复杂度：O(V)，用于存储颜色队列和颜色数组。 关键点 需处理非连通图，确保每个连通分量均被检查。 染色冲突仅发生在发现相邻顶点颜色相同时，无需显式检测奇数环。