企业官网建设流程全解析

leetcode 题解：785. 判断二分图（Is Graph Bipartite）——着色法（DFS）与并查集两种解法详解

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇文章基于 problems/785.is-graph-bipartite.md 展开，系统讲解二分图（Bipartite Graph）的判定问题：从题目给出的邻接表输入出发，先后实现「着色法 + DFS」与「并查集（Union-Find）」两种经典算法，并深入分析各自的时间、空间复杂度。读完本文，你将掌握二分图判定的完整套路，并能将同一套思路无缝迁移到 886. 可能的二分法 等同类题目上。

题目地址与前置知识

• 题目：785. 判断二分图（Is Graph Bipartite）
• 前置知识：图的遍历、DFS（深度优先搜索）

本题与 886 题同属二分图判定套路，本文末尾的「相关问题」小节会给出两题联动练习的指引。此外，仓库中的 thinkings/graph.md 专题系统梳理了建图（邻接矩阵、邻接表）与图的遍历方法，是理解本题解法的基础；thinkings/union-find.md 则对并查集的 find / union / connected 三个核心操作做了详细推导，可作为并查集解法的原理支撑。

题目描述

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集 A 和 B，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，我们就将这个图称为二分图。

graph会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length - 1之间的整数。这图中没有自环和平行边：graph[i]中不存在i，并且graph[i]中没有重复的值。

示例 1：

输入: [[1,3], [0,2], [1,3], [0,2]] 输出: true 解释: 无向图如下: 0----1 | | | | 3----2 我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例 2：

输入: [[1,2,3], [0,2], [0,1,3], [0,2]] 输出: false 解释: 无向图如下: 0----1 | \ | | \ | 3----2 我们不能将节点分割成两个独立的子集。

注意：

• graph的长度范围为[1, 100]。
• graph[i]中的元素的范围为[0, graph.length - 1]。
• graph[i]不会包含i或者有重复的值。
• 图是无向的：如果j在graph[i]里边，那么i也会在graph[j]里边。

从数据结构角度可以这样理解：题目给出的graph本身就是邻接表（Adjacency List），而解法一中的grid则是把邻接表"翻译"成邻接矩阵（Adjacency Matrix）。邻接矩阵graph[i][j] = 1表示顶点 i 与顶点 j 之间有边，0表示无边，这一约定与 thinkings/graph.md 中「图的建立」一节的描述一致。

解法一：着色法 + DFS

求二分图有两种经典思路：一个是着色法，另外一个是并查集。本节先介绍着色法。

思路

着色法的核心直觉是：给每个节点染上两种颜色之一（比如 1 和 -1），并且强制要求相邻节点的颜色必须不同。如果整个图能够被这样染色且不产生冲突，那么染成颜色 1 的节点集合与染成颜色 -1 的节点集合就构成了二分图的两个独立子集 A 和 B。

具体算法：

1. 设置一个长度为 N 的数组colors，colors[i]表示节点i的颜色：0表示无颜色，1表示一种颜色，-1表示另一种颜色。
2. 初始化colors全部为0。
3. 构图（这里是邻接矩阵），使得grid[i][j]表示i和j是否有连接（0表示无，1表示有）。
4. 遍历图：
   • 如果当前节点未染色，则染色，不妨染为颜色1；
   • 递归遍历其邻居：
     • 如果邻居没有染色，则染为另一种颜色，即color * -1，其中color为当前节点的颜色；
     • 否则，判断当前节点和邻居的颜色是否一致，一致则说明冲突，返回False；不一致则继续，返回True。

为什么用0 / 1 / -1而不是0 / 1 / 2？因为当某个节点无法分配当前颜色时，尝试分配另一组颜色只需要乘以 -1即可完成颜色翻转，代码更简洁。这一点在 886 题文档中有同样的说明。

关键点

• 图的建立和遍历
• colors数组（同时承担了 visited 数组的职责，见下文分析）

代码（版本一：先转为邻接矩阵，与 886 题保持一致性）

class Solution: def dfs(self, grid, colors, i, color, N): colors[i] = color for j in range(N): if grid[i][j] == 1: if colors[j] == color: return False if colors[j] == 0 and not self.dfs(grid, colors, j, -1 * color, N): return False return True def isBipartite(self, graph: List[List[int]]) -> bool: N = len(graph) grid = [[0] * N for _ in range(N)] colors = [0] * N for i in range(N): for j in graph[i]: grid[i][j] = 1 for i in range(N): if colors[i] == 0 and not self.dfs(grid, colors, i, 1, N): return False return True

复杂度分析

令 v 和 e 为图中的顶点数和边数。

• 时间复杂度：$O(v+e)$
• 空间复杂度：$O(v)$，其中递归栈深度为 $O(v)$，colors数组长度为 $O(v)$

注意：上面版本构造的邻接矩阵grid是 $O(v^2)$ 的空间开销，但这里按 DFS 遍历的主流程计算渐进复杂度。正如原文档指出，该版本"并不优雅"，其价值在于与 886 题的 DFS 函数保持一致——事实上可以直接把 886 的dfs函数原封不动拿过来用，只需调整graph的构造方式即可。若把邻接矩阵的空间也算进去，最坏（稠密图）可达 $O(v^2)$，886 题的复杂度分析小节给出了这一更精确的说明。

代码（版本二：直接利用邻接表，更优雅）

一个更加优雅的方式是不建立grid，而是直接利用题目给的graph（邻接表）。

class Solution: def isBipartite(self, graph: List[List[int]]) -> bool: n = len(graph) colors = [0] * n def dfs(i, color): colors[i] = color for neibor in graph[i]: if colors[neibor] == color: return False if colors[neibor] == 0 and not dfs(neibor, -1 * color): return False return True for i in range(n): if colors[i] == 0 and not dfs(i, 1): return False return True

关键点：为什么不需要 visited 数组？

很多遍历场景需要visited数组来防止环导致的死循环（thinkings/graph.md 的「图的遍历」一节专门强调过这一点）。但在本题中，colors数组已经同时充当了 visited 的角色：

• 如果colors[i] == 0，说明节点尚未被访问过（等价于visited[i] == False）；
• 否则说明节点已被访问（visited[i] == True）。

因此不需要额外的 visited 数组，代码也避免了「遇到环就死循环」的问题。

关于起始染色的颜色选择

主循环中dfs(i, 1)的初始颜色改成-1是否影响结果？不影响。假设改用-1后的染色分布已知，那么它等价于使用1的情况的反色（颜色 1 与颜色 -1 互换），对"是否二分图"的判断没有任何影响。

那有没有可能使用颜色 1 推出矛盾，而使用颜色 -1 则成立呢？没有可能。因为一次 dfs 处理的是一个连通子图，多次开启 dfs 处理的是互不相交的子图，彼此之间不会产生干扰。原文档给出的验证方法是把主循环随机化起始颜色，例如：

for i in range(n): if random.random() > 0.5: if colors[i] == 0 and not dfs(i, -1): return False else: if colors[i] == 0 and not dfs(i, 1): return False

两种随机策略下答案始终一致，读者可以自行在本地验证这一性质。

解法二：并查集

思路

并查集（Union-Find）解法基于「二分图的互补连通性」这一观察：在二分图中，节点 i 的所有邻居必须处于同一集合（即与 i 互补的那个集合），而 i 自身必须处于另一个集合。

具体算法：

1. 遍历图，对于每一个顶点i，将其所有邻居进行合并，合并到同一个连通域中。
2. 这样当发现某个顶点i和其邻居已经在同一个连通分量的时候，说明它被错误地分到了与邻居相同的集合，直接返回false。
3. 全部遍历完没有冲突，返回true。

这里使用并查集的原因在于：并查集提供find（查找集合代表）、union（合并两个集合）、connected（判断两个元素是否在同一集合）三个近乎 $O(1)$ 的操作，非常适合表达"邻居们必须同属一个集合"这类等价关系。thinkings/union-find.md 中详细推导了这三个操作的实现与优化：find的递归写法会在向上查找的过程中进行路径压缩，把树的高度压到接近 2；union采用按秩合并（小树挂到大树上）保持树的平衡。两者结合后单次操作的时间复杂度可趋近 $O(1)$，这也是并查集解法在稠密图下依然高效的原因。

代码

代码支持：Python3、Java。

Python3 Code：

class UF: def __init__(self, n): self.parent = {} for i in range(n): self.parent[i] = i def union(self, i, j): self.parent[self.find(i)] = self.find(j) def find(self, i): if i == self.parent[i]: return i self.parent[i] = self.find(self.parent[i]) return self.parent[i] def is_connected(self, i, j): return self.find(i) == self.find(j) class Solution: def isBipartite(self, graph: List[List[int]]) -> bool: n = len(graph) uf = UF(n) for i in range(n): for neibor in graph[i]: if uf.is_connected(i, neibor): return False uf.union(graph[i][0], neibor) return True

Java Code（weighted quick-union with path compression）：

class Solution { class UF { int numOfUnions; // number of unions int[] parent; int[] size; UF(int numOfElements) { numOfUnions = numOfElements; parent = new int[numOfElements]; size = new int[numOfElements]; for (int i = 0; i < numOfElements; i++) { parent[i] = i; size[i] = 1; } } // find the head/representative of x int find(int x) { while (x != parent[x]) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; } void union(int p, int q) { int headOfP = find(p); int headOfQ = find(q); if (headOfP == headOfQ) { return; } // connect the small tree to the larger tree if (size[headOfP] < size[headOfQ]) { parent[headOfP] = headOfQ; // set headOfP's parent to be headOfQ size[headOfQ] += size[headOfP]; } else { parent[headOfQ] = headOfP; size[headOfP] += size[headOfQ]; } numOfUnions -= 1; } boolean connected(int p, int q) { return find(p) == find(q); } } public boolean isBipartite(int[][] graph) { int n = graph.length; UF unionfind = new UF(n); // i is what node each adjacent list is for for (int i = 0; i < n; i++) { // i's neighbors for (int neighbor : graph[i]) { // i should not be in the union of its neighbors if (unionfind.connected(i, neighbor)) { return false; } // add into unions unionfind.union(graph[i][0], neighbor); } } return true; } }

Java 版本中的find实现了路径压缩（parent[x] = parent[parent[x]]把节点直接挂到祖父节点上），union则按树的大小（size）把小树挂到大树上，这正是 thinkings/union-find.md 中"路径压缩 + 按秩合并"模板的工程化体现。

复杂度分析

令 v 和 e 为图中的顶点数和边数。

• 时间复杂度：$O(v+e)$。使用 weighted quick-union with path compression 时，union、find和connected均近似 $O(1)$，构建并查集本身需要 $O(v)$。
• 空间复杂度：$O(v)$，用于辅助的并查集空间int[] parent与int[] size。

两种解法对比

从源码结构看，原文档建议将 886 题与本题成对练习：两题共享同一套 DFS 染色逻辑，唯一的差异在于图的输入形式（本题直接给邻接表，886 题给的是"互不喜欢"的边对列表，需要先自行构建邻接矩阵）。把 886 的dfs函数移植到本题几乎不需要改动，这也从侧面印证了"二分图判定 = 建图 + 染色遍历"的统一套路。

仓库中的相关资源

• 题目文档：problems/785.is-graph-bipartite.md
• 关联题目：886. 可能的二分法
• 图论专题：thinkings/graph.md（图的建立、邻接矩阵/邻接表、图的遍历、二分图染色法模板）
• 并查集专题：thinkings/union-find.md（find / union / connected 实现、路径压缩、按秩合并）
• 题库索引：collections/medium.md（本题收录于中等难度题单）、SUMMARY.md

相关问题

• 886. 可能的二分法：输入为"互不喜欢"的边对列表，需要先把边对转成邻接矩阵，再套用与本题完全一致的 DFS 染色逻辑。强烈建议两道题一起练习，巩固二分图判定的完整套路。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode