LeetCode 785. 判断二分图
字数 1455 2025-12-23 07:17:09

LeetCode 785. 判断二分图

题目描述
给定一个无向图，包含 n 个节点（编号从 0 到 n-1）和一个表示边的列表 graph，其中 graph[i] 是一个列表，包含了与节点 i 相邻的所有节点。要求判断这个图是否是二分图。
二分图的定义是：可以将图中的所有节点划分到两个集合中，使得图中任意一条边所连接的两个节点分别属于不同的集合。换句话说，图中不存在长度为奇数的环。

解题过程循序渐进讲解

第一步：理解二分图的核心性质
二分图的等价判定条件之一是“着色可行性”：

  1. 任意选择一个起始节点，将其染成颜色 A。
  2. 与其相邻的所有节点必须染成另一种颜色 B。
  3. 如果染色过程中出现相邻两个节点颜色相同的情况，则说明不是二分图。

这可以用 BFS 或 DFS 对图的连通分量进行染色检查来实现。

第二步：算法设计思路

  1. 图的存储：题目已给出了邻接表 graph，graph[i] 是节点 i 的邻居数组。
  2. 颜色数组：用长度为 n 的数组 color 来标记每个节点的颜色，初始值 0 表示“未染色”，1 和 2 表示两种不同的颜色。
  3. 遍历所有节点：因为图可能不连通，所以需要对每个未访问过的节点都进行一次 BFS/DFS 染色。
  4. 染色规则：从当前节点 u 开始，给它染色（比如颜色 1），然后遍历它的每个邻居 v：
    • 如果 v 未染色，就将其染成与 u 不同的颜色，并加入队列/栈进行下一步扩展。
    • 如果 v 已染色，且颜色与 u 相同，则出现冲突，直接返回 false。
  5. 如果所有连通分量都染色成功，返回 true。

第三步：详细步骤（以 BFS 为例）

  1. 初始化 color 数组长度为 n，全部为 0。
  2. 遍历每个节点 i（0 到 n-1）：
    • 如果 color[i] == 0，说明这个节点属于一个未处理的连通分量，从它开始 BFS。
  3. BFS 过程：
    • 将起始节点 i 入队，并染为 1。
    • 当队列非空时，取出节点 u，遍历它的邻居 v：
      • 如果 color[v] == 0，则 color[v] = 3 - color[u]（即如果 u 是 1，v 是 2；u 是 2，v 是 1），并将 v 入队。
      • 如果 color[v] == color[u]，则返回 false。
  4. 如果 BFS 完成无冲突，继续处理下一个未染色的节点。
  5. 如果所有节点处理完都没有冲突，返回 true。

第四步：举例说明
例1：graph = [[1,3],[0,2],[1,3],[0,2]]

  • 节点0染色1，邻居1、3染色2。
  • 节点1邻居0已染色1（与1不同），邻居2染色1。
  • 节点2邻居1已染色2（不同），邻居3染色2（与2不同）。
  • 节点3邻居0已染色1（与3不同），邻居2已染色1（与3不同）。
  • 全部染色成功，是二分图。

例2：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]（三角形加一个节点）

  • 节点0染色1，邻居1、2、3染色2。
  • 节点1发现邻居2颜色已是2，与1的颜色2相同，冲突，不是二分图。

第五步：复杂度分析

  • 时间复杂度：O(N + E)，N 是节点数，E 是边数，每个节点和边只访问常数次。
  • 空间复杂度：O(N)，用于存储颜色数组和 BFS 队列。

总结
判断二分图的本质是图的二着色问题，利用 BFS/DFS 对连通分量进行交替染色，并检查相邻节点颜色是否不同即可。算法能处理不连通图，且保证每个节点只被处理一次。

LeetCode 785. 判断二分图 题目描述 给定一个无向图，包含 n 个节点（编号从 0 到 n-1）和一个表示边的列表 graph ，其中 graph[i] 是一个列表，包含了与节点 i 相邻的所有节点。要求判断这个图是否是二分图。 二分图的定义是：可以将图中的所有节点划分到两个集合中，使得图中任意一条边所连接的两个节点分别属于不同的集合。换句话说，图中不存在长度为奇数的环。 解题过程循序渐进讲解 第一步：理解二分图的核心性质 二分图的等价判定条件之一是“着色可行性”： 任意选择一个起始节点，将其染成颜色 A。 与其相邻的所有节点必须染成另一种颜色 B。 如果染色过程中出现相邻两个节点颜色相同的情况，则说明不是二分图。 这可以用 BFS 或 DFS 对图的连通分量进行染色检查来实现。 第二步：算法设计思路 图的存储：题目已给出了邻接表 graph ， graph[i] 是节点 i 的邻居数组。 颜色数组：用长度为 n 的数组 color 来标记每个节点的颜色，初始值 0 表示“未染色”，1 和 2 表示两种不同的颜色。 遍历所有节点：因为图可能不连通，所以需要对每个未访问过的节点都进行一次 BFS/DFS 染色。 染色规则：从当前节点 u 开始，给它染色（比如颜色 1），然后遍历它的每个邻居 v： 如果 v 未染色，就将其染成与 u 不同的颜色，并加入队列/栈进行下一步扩展。 如果 v 已染色，且颜色与 u 相同，则出现冲突，直接返回 false 。 如果所有连通分量都染色成功，返回 true 。 第三步：详细步骤（以 BFS 为例） 初始化 color 数组长度为 n，全部为 0。 遍历每个节点 i（0 到 n-1）： 如果 color[i] == 0 ，说明这个节点属于一个未处理的连通分量，从它开始 BFS。 BFS 过程： 将起始节点 i 入队，并染为 1。 当队列非空时，取出节点 u，遍历它的邻居 v： 如果 color[v] == 0 ，则 color[v] = 3 - color[u] （即如果 u 是 1，v 是 2；u 是 2，v 是 1），并将 v 入队。 如果 color[v] == color[u] ，则返回 false 。 如果 BFS 完成无冲突，继续处理下一个未染色的节点。 如果所有节点处理完都没有冲突，返回 true 。 第四步：举例说明 例1： graph = [[1,3],[0,2],[1,3],[0,2]] 节点0染色1，邻居1、3染色2。 节点1邻居0已染色1（与1不同），邻居2染色1。 节点2邻居1已染色2（不同），邻居3染色2（与2不同）。 节点3邻居0已染色1（与3不同），邻居2已染色1（与3不同）。 全部染色成功，是二分图。 例2： graph = [[1,2,3],[0,2],[0,1,3],[0,2]] （三角形加一个节点） 节点0染色1，邻居1、2、3染色2。 节点1发现邻居2颜色已是2，与1的颜色2相同，冲突，不是二分图。 第五步：复杂度分析 时间复杂度：O(N + E)，N 是节点数，E 是边数，每个节点和边只访问常数次。 空间复杂度：O(N)，用于存储颜色数组和 BFS 队列。 总结 判断二分图的本质是图的二着色问题，利用 BFS/DFS 对连通分量进行交替染色，并检查相邻节点颜色是否不同即可。算法能处理不连通图，且保证每个节点只被处理一次。