判断二分图 图解题解

这道题到底在问什么

输入

graph = [[1,3],[0,2],[1,3],[0,2]]

输出

true

输入

graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

输出

false

最优解：一步一步想明白

1. 3相邻必须异色把「分两拨」翻译成「染两种颜色」：相邻的点必须不同色。只要能染成功，就是二分图。
2. 4一个点定了，邻居全被锁死颜色像多米诺骨牌：第一个点一定色，后面全被推着走。所以根本不用试 2 的 n 次方种染法，顺着边「染过去」就行。
3. 5相邻异色，撞色即 false走一遍图，边走边染、相邻就反色；一旦遇到「该反色却已经同色」的边，说明劈不开，直接 false。下面一帧染一个点、一帧查一条边地演给你看。
4. 6color = [_,_,_,_]先把例一画好：四个点围成方框，四条边 0–1、1–2、2–3、3–0。一开始谁都没染色。
5. 7color[0]=A（蓝）· q=[0]随便挑起点 0，给它染上颜色 A（蓝）放进队列。它将带动整个连通块的染色。
6. 8u=0（A）· q=[]从队列取出 0（紫色高亮 = 正在处理）。它是 A，接下来逐条看它的边，邻居都该染成反色 B。
7. 9color[1]=B（绿）· q=[1]看边 0–1（高亮）。1 还没染，染成反色 B（绿）入队。0 蓝、1 绿，这条边合法。
8. 10color[3]=B（绿）· q=[1,3]再看 0 的另一条边 3–0（高亮）。3 也没染，同样染成 B（绿）入队。0 的两条边都跨了色，合法。
9. 11u=1（B）· q=[3]取出 1（B/绿，紫色高亮）。0 退回普通蓝。1 是 B，它的邻居该染成 A。
10. 120=A ≠ 1=B → 合法看边 1–0（高亮）。0 已经染过了，就比一下颜色：0 是 A、1 是 B，不同色，合法，跳过。
11. 13color[2]=A（蓝）· q=[3,2]看边 1–2（高亮）。2 还没染，染成 A（蓝）入队。此刻分组成形：A 拨 = {0,2}，B 拨 = {1,3}。
12. 14已染 {0,1,2,3}· q=[3,2]1 的两条边都查完、没撞色，它处理完毕（变绿）。四个点这下都染上了色，队列里还剩 3、2 等着核对。
13. 15u=3（B）· q=[2]取出 3（B/绿，高亮）。它连 0（A）和 2（A），两条边都已染好（高亮）且颜色都和 3 不同，全合法，无需新染。
14. 16u=2（A）· q=[]取出 2（A/蓝，高亮）。它连 1、3，都是 B，和 2 不同色，合法。队列空了，整张图染完都没撞过色。
15. 17返回 true全染完且从没撞色：A 拨 = {0,2}（蓝），B 拨 = {1,3}（绿）。能干净劈成两拨 → true。
16. 18color 全未染看反例 graph=[[1,2,3],[0,2],[0,1,3],[0,2]]。这里 0、1、2 互相都连，形成一个三角形——它会让染色撞墙。
17. 19color[0]=A（蓝）· q=[0]同样从 0 起步，染A（蓝）入队。它连着 1、2、3 三个点，等会儿出队就会把它们都逼成 B。
18. 20color[1]=B（绿）· q=[1]出队 0（高亮），看边 0–1。1 没染，染 B（绿）入队。0 蓝 1 绿，这条边目前合法。
19. 21color[2]=B（绿）· q=[1,2]再看边 0–2。2 也没染，同样染 B（绿）入队。注意：1 和 2 之间也有一条边，而它俩现在都是绿！
20. 22color[3]=B（绿）· q=[1,2,3]0 的最后一条边 0–3：3 没染，染 B（绿）入队。0 的三个邻居全是 B——隐患已经埋下。
21. 231=B，2=B → 撞色！出队 1（B/绿），查它的边 1–2（高亮）。可 2 也是 B（绿）！相邻两点同色，这条边劈不开，立刻返回 false。
22. 24有奇环 ⇔ 非二分图记住这个结论：一张图是二分图，当且仅当它没有奇数长度的环。三角形就是最小的奇环，所以反例必然 false。
23. 27遍历每个未染点 + BFS 染色凡是「分两组 / 相邻不同 / 站队对立」的题，都能套这个两色染色模板。
24. 29第一块 {0,1} 已染这张图分两块：{0,1} 和 {2,3,4}。从 0 跑只染好了上面一块，第二块 2、3、4 还全是灰的。
25. 30从 2 重启 BFS，全染好外层 for 走到没染的 2，重启一次 BFS 把第二块也染好（2、4 蓝，3 绿）。这就是为什么必须遍历每个点。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from collections import deque
class Solution:
    def isBipartite(self, graph):
        n = len(graph)
        color = [0] * n          # 0 未染, 1/-1 两色
        for s in range(n):       # 每个连通块各跑一次
            if color[s] != 0:
                continue
            color[s] = 1
            q = deque([s])
            while q:
                u = q.popleft()
                for v in graph[u]:
                    if color[v] == 0:        # 没染 → 染反色
                        color[v] = -color[u]
                        q.append(v)
                    elif color[v] == color[u]:  # 撞色
                        return False
        return True

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, 0);
        for (int s = 0; s < n; s++) {
            if (color[s] != 0) continue;
            color[s] = 1;
            queue<int> q;
            q.push(s);
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : graph[u]) {
                    if (color[v] == 0) {
                        color[v] = -color[u];
                        q.push(v);
                    } else if (color[v] == color[u]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
};

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        for (int s = 0; s < n; s++) {
            if (color[s] != 0) continue;
            color[s] = 1;
            Deque<Integer> q = new ArrayDeque<>();
            q.offer(s);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : graph[u]) {
                    if (color[v] == 0) {
                        color[v] = -color[u];
                        q.offer(v);
                    } else if (color[v] == color[u]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

复杂度

面试官可能追问