LeetCode 785. 判断二分图
目录
题目描述
题意分析
输入是一张无向图的邻接表
graph，graph[u]列出了和u相连的所有点。要判断能不能把所有节点划进两个集合，使得每条边的两个端点分属不同集合。「分成两组，边只跨组不组内」这句话换个说法就是：给每个点涂上两种颜色之一，任意一条边的两端颜色必须不同。判定问题于是变成了「这张图能不能用两种颜色正确着色」。
约束信号有几处必须抓住。第一，图不保证连通，
graph里可能有好几团互相独立的点，只从0号点出发会漏掉其他团。第二，题目保证无自环、无重边，所以不必担心u自己连自己这种必然失败的情形。第三，邻接表是对称存储的，v在graph[u]里就意味着u也在graph[v]里，同一条边会被两端各看到一次。边界上要留意：孤立点（邻接表为空，任意涂色都合法）、整张图没有边（一定是二分图）、以及包含奇数长度环的情形（一定不是二分图）。
解法：BFS 染色
核心思路
暴力做法是枚举每个点归到哪一组，$2^n$ 种划分逐一检查所有边是否合法。
n到100时这条路完全走不通。瓶颈在于这些划分之间存在大量强制关系被浪费了：一旦某个点的颜色定下来，与它相邻的点的颜色就完全没有自由度，必须取相反色；再往外传播，整个连通块的着色方案就被这一个点锁死了。换句话说，一个连通块最多只有两种可能的着色（互为颜色翻转），而这两种在合法性上完全等价。自由度从 $2^n$ 塌缩到了「每个连通块任选一个起点随便涂一种色」。
观察到这一点，做法就固定下来：从每个还没涂色的点出发，把它涂成
1，然后沿着边把「相反色」逐层传播出去。传播过程中每遇到一条边，都要检查两端是否真的异色；只要有一条边的两端同色，说明这个连通块的着色被逼出了矛盾，而前面已经论证了着色方案本质唯一，所以矛盾不可调和，整张图不是二分图。用
color[i]表示节点颜色：0表示还没涂，1和-1表示两种颜色。选这套编码是因为取相反色可以直接写成-color[u]，比布尔数组再配一个visited数组省一半状态。显式的不变量是：任意时刻，所有
color非0的节点之间，凡是已经被检查过的边，两端颜色都不同；并且同一个连通块内已涂色的点，其颜色关系由起点唯一确定。BFS 结束时每条边都恰好被两端各检查过一次，不变量就升级成了完整的二分图证明。
解题步骤
- 开一个长度为
n的color数组并全部置0。这个数组同时承担「访问标记」和「颜色记录」两个职责，用0表示未访问可以省掉单独的visited。- 外层从
0到n - 1遍历所有节点，跳过已经涂过色的。这一层循环存在的唯一理由就是图可能不连通，少了它会漏掉除起点所在块以外的全部连通块。- 遇到未涂色的点就把它当作新连通块的起点，涂成
1并推进队列。起点涂什么颜色无所谓，因为整块颜色翻转不影响合法性。- 队列非空时弹出一个点
node，遍历graph[node]里的每个邻居next。- 若
color[next] == 0，把它涂成-color[node]并入队。涂色和入队必须一起做，否则同一个点可能被多次推进队列。- 若
color[next] != 0且等于color[node]，立刻返回false。这是唯一的失败出口，对应发现了一条同色边。- 所有连通块都跑完还没返回
false，就返回true。以
graph = [[1, 3], [0, 2], [1, 3], [0, 2]]走一遍：这是一个四元环0-1-2-3-0，n = 4，color初始为[0, 0, 0, 0]。外层
start = 0，未涂色，涂成1，color = [1, 0, 0, 0]，队列是[0]。弹出
0，邻居是1和3。color[1]是0，涂成-1并入队；color[3]是0，也涂成-1并入队。此时color = [1, -1, 0, -1]，队列是[1, 3]。弹出
1，邻居是0和2。color[0] = 1与color[1] = -1不同，检查通过；color[2]是0，涂成-color[1] = 1并入队。此时color = [1, -1, 1, -1]，队列是[3, 2]。弹出
3，邻居是0和2。color[0] = 1与color[3] = -1不同，通过；color[2] = 1与-1不同，通过。队列是[2]。弹出
2，邻居是1和3，颜色都是-1，与color[2] = 1不同，全部通过。队列清空。外层继续走
start = 1、2、3，它们的颜色都已非0，全部跳过。最终返回true，两组分别是{0, 2}和{1, 3}。再看失败用例
graph = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]：0涂1，它的三个邻居1、2、3全部涂-1。弹出1时先看邻居0，颜色1与-1不同没问题；再看邻居2，color[2] = -1恰好等于color[1] = -1，边1-2两端同色，立刻返回false——这条边和0-1、0-2一起构成了三元环，奇环注定无法二着色。
代码实现
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n];
for (int start = 0; start < n; start++) {
if (color[start] != 0) {
continue;
}
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(start);
color[start] = 1;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int next : graph[node]) {
if (color[next] == 0) {
color[next] = -color[node];
queue.offer(next);
} else if (color[next] == color[node]) {
return false;
}
}
}
}
return true;
}
}
func isBipartite(graph [][]int) bool {
n := len(graph)
color := make([]int, n)
for start := 0; start < n; start++ {
if color[start] != 0 {
continue
}
queue := []int{start}
color[start] = 1
for head := 0; head < len(queue); head++ {
node := queue[head]
for _, next := range graph[node] {
if color[next] == 0 {
color[next] = -color[node]
queue = append(queue, next)
} else if color[next] == color[node] {
return false
}
}
}
}
return true
}
复杂度分析
- 时间复杂度：$O(n + e)$，
n是节点数，e是边数。每个节点最多入队一次（入队的同时就被涂色，涂过色的不会再入队），出队后遍历它的邻接表，所有邻接表长度之和是 $2e$，因此边的检查总次数是 $O(e)$；外层那趟找起点的循环额外贡献 $O(n)$。- 空间复杂度：$O(n)$，
color数组占n格，BFS 队列在最坏情况下（某一层几乎装下整个连通块）也是 $O(n)$。邻接表是输入自带的，不计入额外空间。
关键点总结
- 判定类的图论题，先找「自由度会不会塌缩」。这题看似有 $2^n$ 种分组，但一个连通块只要定下一个点的颜色，其余全部被边强制推导出来，自由度实际只有「每个块二选一」，而这两个选择还等价。识别出这一点，指数搜索立刻变成一次遍历。
- 把
visited和状态值合并成一个数组，是图搜索里常用的省事技巧。这里用0/1/-1三态，既省了一个数组，取相反色还能直接写成取负号。- 「图可能不连通」是所有图遍历题的默认假设，除非题目明确说连通。外层那圈找未访问起点的循环应该成为肌肉记忆，而不是被用例卡住之后才补上。
- 冲突检查必须写在「邻居已涂色」这个分支里。只在涂色时传播、不在相遇时比对，等于只建关系不做验证，任何图都会被判成二分图。
- 面试视角：面试官常追问「二分图和奇环是什么关系」。标准回答是一张图是二分图当且仅当它不含奇数长度的环，染色冲突发生的位置正对应着某个奇环被闭合的那一刻。能把判定条件和图论性质对上，比只会背模板强得多。
- 面试视角：另一个高频追问是「能不能用并查集」。可以——把每个点拆成「本体」和「对立面」两个副本，对每条边合并
u的本体与v的对立面、v的本体与u的对立面，一旦某个点的本体和对立面被合进同一集合就返回false。顺手提一句 DFS 版本只需把队列换成递归栈，也能显示解法之间的通用性。
易错点总结
- 错误写法：只从节点
0开始 BFS，不做外层的起点扫描。用例graph = [[], [2, 3], [1, 3], [1, 2]]→ 节点0是孤立点，BFS 一步就结束并返回true，而节点1、2、3构成三元环根本不是二分图，正确答案是false。- 错误写法：只在邻居未涂色时传播颜色，忘了写已涂色时的同色检查。用例
graph = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]→ 每个点都被顺利涂上色，没有任何分支能返回false，函数返回true，正确答案是false。- 错误写法：把冲突条件写成
color[next] != -color[node]却又允许color[next] == 0进入这一支。用例graph = [[1, 3], [0, 2], [1, 3], [0, 2]]→ 第一次遇到未涂色的邻居1时0 != -1成立，直接返回false，而这张四元环图本是二分图，正确答案是true。- 错误写法：给邻居涂色时忘了取反，写成
color[next] = color[node]。用例graph = [[1, 3], [0, 2], [1, 3], [0, 2]]→ 节点1和3都被涂成和0一样的1，弹出1后检查邻居0立刻发现同色，返回false，正确答案是true。- 错误写法：
color数组的长度取成graph[0].length而不是graph.length。用例graph = [[], [2, 3], [1, 3], [1, 2]]→graph[0]是空表，数组长度被开成0，第一次访问color[0]就抛出越界。- 错误写法：外层循环的跳过条件写成
if (color[start] == 1) continue;。用例graph = [[1, 3], [0, 2], [1, 3], [0, 2]]→ 涂成-1的节点1和3没被跳过，会被当成新起点重新涂成1，与已有的-1冲突，返回false，正确答案是true。- 错误写法：把邻接表当成有向图，认为边
u → v检查过就不必再从v检查回u，于是遍历时跳过「已涂色」的所有邻居。这等价于删掉了冲突检查，用例graph = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]→ 返回true，正确答案是false。- 错误写法：为了写 DFS 版本而在递归里先返回
true再递归下去，没有把子调用的false向上传播。用例graph = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]→ 深层发现的冲突被丢弃，最外层照样返回true，正确答案是false。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 886. 可能的二分法 | 中等 | 图以「互相讨厌」的边对给出，需要先自己建邻接表再染色 |
| LCR 106. 判断二分图 | 中等 | 同题的另一入口，适合用来对照 BFS 与 DFS 两种传播写法 |
| 547. 省份数量 | 中等 | 同样要处理不连通的图，但目标是数连通块而不是验证约束 |
| 990. 等式方程的可满足性 | 中等 | 相等与不等两类约束，用并查集先合并后验证，是染色的对偶思路 |