LeetCode 785. 判断二分图 题目描述 给定一个无向图，包含 n 个节点（编号从 0 到 n-1）和一个边的列表。请判断这个图是否是二分图。二分图的定义是：能够将图中的所有节点分成两个独立的集合 U 和 V，使得每条边都连接 U 中的一个节点和 V 中的一个节点（即不存在连接同一集合内两个节点的边）。 示例 输入：graph = [ [ 1,2,3],[ 0,2],[ 0,1,3],[ 0,2] ] 输出：false 解释：无法将节点分成两个集合使得每条边都跨集合连接。例如，节点 0 与 1、2、3 相连，但 1 和 2 之间也有边，导致冲突。 解题过程 1. 核心思路 二分图的判断等价于图的二着色问题：尝试用两种颜色（例如 0 和 1）对节点进行染色，使得相邻节点颜色不同。如果能够完成染色，则是二分图；否则不是。 2. 算法选择 常用深度优先搜索（DFS）或广度优先搜索（BFS）遍历图，在遍历过程中进行染色检查： 初始化一个颜色数组 color[] ，初始值为 -1（未染色）。 遍历每个节点，若未染色，则从该节点开始 DFS/BFS，将其染成颜色 0，然后将其邻居染成颜色 1，邻居的邻居染成颜色 0，依此类推。 如果在染色过程中发现某个邻居的颜色与当前节点相同，则说明冲突，返回 false。 如果所有节点成功染色且无冲突，返回 true。 3. 详细步骤（以 BFS 为例） 步骤 1：创建颜色数组 color ，长度等于节点数 n，初始值全为 -1。 步骤 2：遍历每个节点 i（0 到 n-1）： 如果 color[i] == -1 （未访问），将其加入队列，并染成颜色 0。 开始 BFS： a. 从队列取出节点 u，检查其所有邻居 v： b. 如果 v 未染色（ color[v] == -1 ），将其染成与 u 相反的颜色（ color[v] = 1 - color[u] ），并加入队列。 c. 如果 v 已染色且 color[v] == color[u] ，说明冲突，直接返回 false。 步骤 3：若所有节点处理完毕且无冲突，返回 true。 4. 示例推导（graph = [ [ 1,2,3],[ 0,2],[ 0,1,3],[ 0,2]]） 初始化 color = [-1, -1, -1, -1] 。 从节点 0 开始 BFS： 染 color[ 0] = 0，邻居 [ 1,2,3 ] 应染为 1。 处理节点 1：color[ 1] = 1，邻居 [ 0,2] 中，0 已染色且颜色不同（0≠1），合法；2 未染色，染 color[ 2 ] = 0。 处理节点 2：color[ 2] = 0，邻居 [ 0,1,3 ] 中，0 颜色不同（0=0? 冲突！因为 0 和 2 都是颜色 0，但二者有边连接），返回 false。 5. 复杂度分析 时间复杂度：O(n + e)，其中 n 是节点数，e 是边数（每个节点和边各访问一次）。 空间复杂度：O(n)，用于存储颜色数组和队列。 关键点 二分图可能不是连通图，因此需要遍历每个未访问的节点作为 BFS/DFS 的起点。 染色规则必须严格保证相邻节点颜色互异。