跳到主要内容

LeetCode 785. 判断二分图

本节目标

对每个连通分量进行 BFS 二染色，发现相邻同色即判定不是二分图。

这是连通性、并查集与二分图中“相邻必须分到不同组”的母题。二分图不是要求图连通，而是要求每个连通分量都能被二染色。

查看 LeetCode 原题

题意与约束​

邻接表 graph[u] 给出 u 的无向邻居。若所有边都能跨越两组，图是二分图；任意奇数长度环都会迫使起点最后与自己同色。孤立点没有边，可单独归入任意一组。重要的是：一个不含奇环的首分量不能证明整个图二分，后面的独立分量仍须检查。

直接思路与瓶颈​

若枚举每个顶点属于两组的所有可能，n 个顶点有 2^n 种分法；仅靠局部猜测也可能在远处遇到同色相邻才发现矛盾。沿边传播“邻居必须相反”的颜色，可以一次遍历就记录并检验全部约束。

图模型与算法推导​

用 -1 表示未染色，0、1 表示两组。对每个未染色起点，把它染为 0 并 BFS。队列中及已访问的每条边都满足“已确定的相邻点颜色不同”：遇到未染色邻居就赋为 1 - color[u]，遇到已染色邻居则检查它不能与 u 同色。

如果一条边两端同色，沿 BFS 树从该分量起点到两个端点的路径会与这条边拼出奇环，约束矛盾；没有矛盾时，颜色数组本身就是一个合法划分。

正确性依据​

对一个 BFS 分量，起点任取 0 不影响可行性。每次沿边为未染色邻居设置相反色，保持已处理边跨组；若已有邻居同色，任何二分划分都会违反该边，返回假正确。外层循环启动所有未染色分量，所以无一遗漏。全部遍历后颜色给出每条边的两端不同色，图为二分图。

样例执行过程​

以三角形 graph = [[1,2],[0,2],[0,1]] 为例，初始 color = [0,-1,-1]、pending = [0]。弹出 0 后，邻居 1、2 都必须染成与 0 相反的颜色 1，此时 color = [0,1,1]、队列含 1、2。随后弹出 1：边 (1,0) 两端颜色不同，没有冲突；检查边 (1,2) 时发现两端都为 1，说明这个奇环无法二染色，立即返回 false。

代码实现​

C++17
#include <queue>
#include <vector>
using namespace std;

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

行为测试先放入含两条独立边和孤立点的合法图，再把奇环放在第一个分量之外，确保实现会从每个未染色顶点启动 BFS。

复杂度分析​

每个顶点最多入队一次，每条无向边从邻接表两端各检查一次，时间 O(n + m)；颜色和队列使用 O(n) 额外空间。

边界与易错点​

  • 外层循环必须遍历所有顶点，而非只从 0 开始。
  • 染色应在入队时完成，避免同一节点被多个邻居重复入队。
  • 相邻已染色节点的颜色相同才失败；不同色应继续。
  • 空图和只含孤立点的图都是二分图。

模式迁移​

“敌人必须不同阵营”“相邻任务不能同班”都可转成二染色。若还需按距离分层，BFS 队列天然携带层序；若约束变为多种颜色或不等式，需考虑更一般的图着色或约束满足模型。