Medium

题目描述

有一个无向图，图中有 n 个节点，节点编号从 0 到 n - 1。给定一个二维数组 graph，其中 graph[u] 是与节点 u 相邻的节点数组。更正式地说，对于 graph[u] 中的每个 v，节点 u 和节点 v 之间都有一条无向边。该图具有以下属性：

  • 没有自环（graph[u] 不包含 u）
  • 没有平行边（graph[u] 不包含重复值）
  • 如果 v 在 graph[u] 中，那么 u 在 graph[v] 中（图是无向的）
  • 图可能不连通，意味着可能存在两个节点 u 和 v，它们之间没有路径

如果能将图的节点分割成两个独立的集合 A 和 B，使得图中的每条边都连接集合 A 中的一个节点和集合 B 中的一个节点，那么这个图就是二分图。

当且仅当图是二分图时返回 true。

示例 1：

输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
输出：false
解释：无法将节点分割成两个独立的集合，使得每条边都连接两个不同集合中的节点。

示例 2：

输入：graph = [[1,3],[0,2],[1,3],[0,2]]
输出：true
解释：我们可以将节点分成两个集合：{0, 2} 和 {1, 3}。

约束条件：

  • graph.length == n
  • 1 <= n <= 100
  • 0 <= graph[u].length < n
  • 0 <= graph[u][i] <= n - 1
  • graph[u] 不包含 u
  • graph[u] 的所有值都是唯一的
  • 如果 graph[u] 包含 v，那么 graph[v] 包含 u

解题思路

判断二分图的核心思想是图着色问题：尝试用两种颜色给图中所有节点着色，使得相邻节点颜色不同。

主要思路：

  1. 图着色策略：使用两种颜色（0和1）给节点着色，相邻节点必须是不同颜色
  2. 遍历策略：由于图可能不连通，需要遍历所有未访问的节点作为起点
  3. 冲突检测：如果发现相邻节点颜色相同，说明不是二分图

常见解法：

  • BFS解法：使用队列层序遍历，逐层着色相邻节点
  • DFS解法：使用递归深度优先遍历，递归着色相邻节点
  • 并查集解法：将相邻节点分到不同集合中

推荐解法：DFS，代码简洁且直观。算法流程：

  1. 初始化颜色数组，-1表示未着色
  2. 遍历所有节点，对未着色节点进行DFS着色
  3. DFS过程中，给当前节点着色，然后检查所有相邻节点：
    • 如果相邻节点未着色，递归着色为相反颜色
    • 如果相邻节点已着色且颜色相同，返回false
  4. 所有节点都能正确着色则返回true

代码实现

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, -1);
        
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                if (!dfs(graph, color, i, 0)) {
                    return false;
                }
            }
        }
        return true;
    }
    
private:
    bool dfs(vector<vector<int>>& graph, vector<int>& color, int node, int c) {
        color[node] = c;
        for (int neighbor : graph[node]) {
            if (color[neighbor] == c) {
                return false;
            }
            if (color[neighbor] == -1 && !dfs(graph, color, neighbor, 1 - c)) {
                return false;
            }
        }
        return true;
    }
};

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

public class Solution {
    public bool IsBipartite(int[][] graph) {
        int n = graph.Length;
        int[] color = new int[n];
        Array.Fill(color, -1);
        
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                if (!Dfs(graph, color, i, 0)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private bool Dfs(int[][] graph, int[] color, int node, int c) {
        color[node] = c;
        foreach (int neighbor in graph[node]) {
            if (color[neighbor] == c) {
                return false;
            }
            if (color[neighbor] == -1 && !Dfs(graph, color, neighbor, 1 - c)) {
                return false;
            }
        }
        return true;
    }
}

var isBipartite = function(graph) {
    const n = graph.length;
    const colors = new Array(n).fill(-1);
    
    for (let i = 0; i < n; i++) {
        if (colors[i] === -1) {
            const queue = [i];
            colors[i] = 0;
            
            while (queue.length > 0) {
                const node = queue.shift();
                
                for (const neighbor of graph[node]) {
                    if (colors[neighbor] === -1) {
                        colors[neighbor] = 1 - colors[node];
                        queue.push(neighbor);
                    } else if (colors[neighbor] === colors[node]) {
                        return false;
                    }
                }
            }
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(V + E)V是节点数，E是边数，每个节点和边都访问一次
空间复杂度O(V)需要颜色数组存储每个节点的着色状态，递归栈深度最大为V

相关题目