LeetCode 785. 判断二分图

约 5 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 微软
标签
深度优先搜索 广度优先搜索 图 并查集

题目描述

✅ 785. 判断二分图

image-20260929000226091

image-20260929000226092

image-20260929000226093

题意分析

判断无向图的所有节点能否分成两组，使每条边的两个端点属于不同组。两组内部不能有边，但同组节点不需要彼此连通。图可能包含多个连通分量和孤立点，必须全部检查。

解法：BFS 染色

核心思路

[!blue]

用 color[node] 记录分组：0 表示尚未分组，1 和 -1 表示两种颜色。任选一个未染色节点作为起点，设为 1；沿边搜索时，邻居必须与当前节点颜色相反，因此未染色邻居只能设为 -color[node]。

同一连通分量中，一旦确定起点颜色，沿搜索路径到达的每个节点就被交替关系确定。若一条边的两端已经同色，说明这些约束无法同时满足；将起点改成另一种颜色只会使整片分量的颜色一起翻转，这条边仍然同色，所以无需尝试另一种起点颜色，直接返回 false。

若所有边都检查完且没有冲突，按两种颜色划分节点后，每条边都跨越两组，便满足二分图定义。不同连通分量之间没有边，可以独立染色；外层遍历每个节点，为尚未染色的分量重新启动 BFS。

解题步骤

  • 初始化全零颜色数组，依次检查每个节点。
  • 已染色节点所属的分量已经处理过，跳过；未染色节点设为 1 并加入队列。
  • 出队一个节点，遍历它的邻居。未染色邻居立即染相反色并入队；已染色邻居若与它同色，立即返回 false。
  • 当前队列为空后继续寻找下一分量。所有分量都无冲突时返回 true；孤立点没有邻边，自然通过检查。

代码实现

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
}

复杂度分析

设节点数为 V、无向边数为 E。

  • 时间复杂度：$O(V+E)$。每个节点只入队一次，每条无向边在两个端点的邻接表中各检查一次。
  • 空间复杂度：$O(V)$。颜色数组保存所有节点状态，队列最多保存一个连通分量的节点。

关键点总结

[!green]

  • 颜色数组同时记录访问状态和分组，不需要额外的访问数组。
  • 沿边染相反色体现分组约束，检查已染色邻居才能发现矛盾。
  • 各分量可以任意选择起始颜色，但每个分量都必须检查。

易错点总结

[!yellow]

  • 只从零号节点搜索，可能漏掉其他连通分量中的冲突。
  • 不能直接跳过所有已染色邻居；它的颜色是否与当前节点相反，正是需要验证的条件。
  • 邻居必须在入队时染色，避免多个节点把同一个未染色邻居重复入队。
  • 起点颜色没有好坏之分；同一分量整体交换两种颜色，不会改变边是否冲突。

相似题目

题目 难度 关联与区别
886. 可能的二分法 中等 把不喜欢关系建成无向图后，能否分成两组就是同一个二分图染色判定。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/18421836
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！