二分图判定算法

数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode 力扣 难度
785. Is Graph Bipartite? 785. 判断二分图 🟠
886. Possible Bipartition 886. 可能的二分法 🟠
- 剑指 Offer II 106. 二分图 🟠

———–

本文有视频版： 二分图判定算法及应用。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

我之前写了好几篇图论相关的文章：

图遍历算法

名流问题

并查集算法计算连通分量

环检测和拓扑排序

Dijkstra 最短路径算法

今天继续来讲一个经典图论算法：二分图判定。

二分图简介

在讲二分图的判定算法之前，我们先来看下百度百科对「二分图」的定义：

二分图的顶点集可分割为两个互不相交的子集，图中每条边依附的两个顶点都分属于这两个子集，且两个子集内的顶点不相邻。

其实图论里面很多术语的定义都比较拗口，不容易理解。我们甭看这个死板的定义了，来玩个游戏吧：

给你一幅「图」，请你用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同，你能做到吗？

这就是图的「双色问题」，其实这个问题就等同于二分图的判定问题，如果你能够成功地将图染色，那么这幅图就是一幅二分图，反之则不是：

在具体讲解二分图判定算法之前，我们先来说说计算机大佬们闲着无聊解决双色问题的目的是什么。

首先，二分图作为一种特殊的图模型，会被很多高级图算法（比如最大流算法）用到，不过这些高级算法我们不是特别有必要去掌握，有兴趣的读者可以自行搜索。

从简单实用的角度来看，二分图结构在某些场景可以更高效地存储数据。

比如说我们需要一种数据结构来储存电影和演员之间的关系：某一部电影肯定是由多位演员出演的，且某一位演员可能会出演多部电影。你使用什么数据结构来存储这种关系呢？

既然是存储映射关系，最简单的不就是使用哈希表嘛，我们可以使用一个 HashMap<String, List<String>> 来存储电影到演员列表的映射，如果给一部电影的名字，就能快速得到出演该电影的演员。

但是如果给出一个演员的名字，我们想快速得到该演员演出的所有电影，怎么办呢？这就需要「反向索引」，对之前的哈希表进行一些操作，新建另一个哈希表，把演员作为键，把电影列表作为值。

显然，如果用哈希表存储，需要两个哈希表分别存储「每个演员到电影列表」的映射和「每部电影到演员列表」的映射。但如果用「图」结构存储，将电影和参演的演员连接，很自然地就成为了一幅二分图：

每个电影节点的相邻节点就是参演该电影的所有演员，每个演员的相邻节点就是该演员参演过的所有电影，非常方便直观。

再举个近在眼前的例子，我的网站每篇文章末尾都会有引用该文章的题目，这就是二分图的应用：

「文章」和「题目」就可以抽象成「图」中两种不同的节点类型，文章和题目之间的引用可以抽象成边，这就是标准的二分图模型，只要查询任意一个「文章」节点即可得到关联的「题目」节点，查询任意一个「题目」节点，即可得到关联的「文章」节点。

其实生活中不少实体的关系都能自然地形成二分图结构，所以在某些场景下图结构也可以作为存储键值对的数据结构（符号表）。

好了，接下来进入正题，说说如何判定一幅图是否是二分图。

二分图判定思路

判定二分图的算法很简单，就是用代码解决「双色问题」。

说白了就是遍历一遍图，一边遍历一边染色，看看能不能用两种颜色给所有节点染色，且相邻节点的颜色都不相同。

既然说到遍历图，也不涉及最短路径之类的，当然是 DFS 算法和 BFS 皆可了，DFS 算法相对更常用些，所以我们先来看看如何用 DFS 算法判定双色图。

首先，基于 学习数据结构和算法的框架思维 写出图的遍历框架：

/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    if (root == null) return;
    traverse(root.left);
    traverse(root.right);
}

/* 多叉树遍历框架 */
void traverse(Node root) {
    if (root == null) return;
    for (Node child : root.children)
        traverse(child);
}

/* 图遍历框架 */
boolean[] visited;
void traverse(Graph graph, int v) {
    // 防止走回头路进入死循环
    if (visited[v]) return;
    // 前序遍历位置，标记节点 v 已访问
    visited[v] = true;
    for (Vertex neighbor : graph.neighbors(v))
        traverse(graph, neighbor);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 二叉树遍历框架
void traverse(TreeNode* root) {
    if (root == nullptr) return;
    traverse(root->left);
    traverse(root->right);
}

// 多叉树遍历框架
void traverse(Node* root) {
    if (root == nullptr) return;
    for (Node* child : root->children)
        traverse(child);
}

// 图遍历框架
vector<bool> visited;
void traverse(Graph* graph, int v) {
    // 防止走回头路进入死循环
    if (visited[v]) return;
    // 前序遍历位置，标记节点 v 已访问
    visited[v] = true;
    for (Vertex neighbor : graph->neighbors(v))
        traverse(graph, neighbor);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

# 二叉树遍历框架
def traverse(root):
    if not root:
        return
    traverse(root.left);
    traverse(root.right);

# 多叉树遍历框架
def traverse(root):
    if not root:
        return
    for child in root.children:
        traverse(child)

# 图遍历框架
def traverse(graph, v):
    global visited
    # 防止走回头路进入死循环
    if visited[v]: 
        return
    # 前序遍历位置，标记节点 v 已访问
    visited[v] = True
    for neighbor in graph.neighbors(v):
        traverse(graph, neighbor)

visited = []

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 二叉树遍历框架
func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    traverse(root.Right)
}

// 多叉树遍历框架
func traverse(root *Node) {
    if root == nil {
        return
    }
    for _, child := range root.Children {
        traverse(child)
    }
}

// 图遍历框架
var visited map[int]bool

func traverse(graph *Graph, v int) {
    // 防止走回头路进入死循环
    if visited[v] {
        return
    }
    // 前序遍历位置，标记节点 v 已访问
    visited[v] = true
    for _, neighbor := range graph.Neighbors(v) {
        traverse(graph, neighbor)
    }
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

/* 二叉树遍历框架 */
var traverse = function(root) {
    if (root === null) return;
    traverse(root.left);
    traverse(root.right);
}

/* 多叉树遍历框架 */
var traverse = function(root) {
    if (root === null) return;
    for (var i = 0; i < root.children.length; i++) {
        var child = root.children[i];
        traverse(child);
    }
}

/* 图遍历框架 */
var visited = [];
var traverse = function(graph, v) {
    // 防止走回头路进入死循环
    if (visited[v]) return;
    // 前序遍历位置，标记节点v已访问
    visited[v] = true;
    for (var i = 0; i < graph.neighbors(v).length; i++) {
        var neighbor = graph.neighbors(v)[i];
        traverse(graph, neighbor);
    }
}

因为图中可能存在环，所以用 visited 数组防止走回头路。

这里可以看到我习惯把 return 语句都放在函数开头，因为一般 return 语句都是 base case，集中放在一起可以让算法结构更清晰。

其实，如果你愿意，也可以把 if 判断放到其它地方，比如图遍历框架可以稍微改改：

/* 图遍历框架 */
boolean[] visited;
void traverse(Graph graph, int v) {
    // 前序遍历位置，标记节点 v 已访问
    visited[v] = true;
    for (int neighbor : graph.neighbors(v)) {
        if (!visited[neighbor]) {
            // 只遍历没标记过的相邻节点
            traverse(graph, neighbor);
        }
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

/* 图遍历框架 */
vector<bool> visited;
void traverse(Graph graph, int v) {
    // 前序遍历位置，标记节点 v 已访问
    visited[v] = true;
    for (int neighbor : graph.neighbors(v)) {
        if (!visited[neighbor]) {
            // 只遍历没标记过的相邻节点
            traverse(graph, neighbor);
        }
    }
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

visited = []
def traverse(graph: Graph, v: int) -> None:
    # 前序遍历位置，标记节点 v 已访问
    visited[v] = True
    for neighbor in graph.neighbors(v):
        if not visited[neighbor]:
            # 只遍历没标记过的相邻节点
            traverse(graph, neighbor)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 图遍历框架 
var visited []bool

func traverse(graph Graph, v int) {
    // 前序遍历位置，标记节点 v 已访问
    visited[v] = true
    for _, neighbor := range graph.neighbors(v) {
        if !visited[neighbor] {
            // 只遍历没标记过的相邻节点
            traverse(graph, neighbor)
        }
    }
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

/* 图遍历框架 */
var visited = [];
var traverse = function(graph, v) {
    // 前序遍历位置，标记节点 v 已访问
    visited[v] = true;
    for (let neighbor of graph.neighbors(v)) {
        if (!visited[neighbor]) {
            // 只遍历没标记过的相邻节点
            traverse(graph, neighbor);
        }
    }
};

这种写法把对 visited 的判断放到递归调用之前，和之前的写法唯一的不同就是，你需要保证调用 traverse(v) 的时候，visited[v] == false。

为什么要特别说这种写法呢？因为我们判断二分图的算法会用到这种写法。

回顾一下二分图怎么判断，其实就是让 traverse 函数一边遍历节点，一边给节点染色，尝试让每对相邻节点的颜色都不一样。

所以，判定二分图的代码逻辑可以这样写：

/* 图遍历框架 */
void traverse(Graph graph, boolean[] visited, int v) {
    visited[v] = true;
    // 遍历节点 v 的所有相邻节点 neighbor
    for (int neighbor : graph.neighbors(v)) {
        if (!visited[neighbor]) {
            // 相邻节点 neighbor 没有被访问过
            // 那么应该给节点 neighbor 涂上和节点 v 不同的颜色
            traverse(graph, visited, neighbor);
        } else {
            // 相邻节点 neighbor 已经被访问过
            // 那么应该比较节点 neighbor 和节点 v 的颜色
            // 若相同，则此图不是二分图
        }
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 图遍历框架
void traverse(Graph graph, bool visited[], int v) {
    visited[v] = true;
    // 遍历节点 v 的所有相邻节点 neighbor
    for (int neighbor : graph.neighbors(v)) {
        if (!visited[neighbor]) {
            // 相邻节点 neighbor 没有被访问过
            // 那么应该给节点 neighbor 涂上和节点 v 不同的颜色
            traverse(graph, visited, neighbor);
        } else {
            // 相邻节点 neighbor 已经被访问过
            // 那么应该比较节点 neighbor 和节点 v 的颜色
            // 若相同，则此图不是二分图
        }
    }
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

# 图遍历框架
def traverse(graph, visited, v):
    visited[v] = True
    # 遍历节点 v 的所有相邻节点 neighbor
    for neighbor in graph.neighbors(v):
        if not visited[neighbor]:
            # 相邻节点 neighbor 没有被访问过
            # 那么应该给节点 neighbor 涂上和节点 v 不同的颜色
            traverse(graph, visited, neighbor)
        else:
            # 相邻节点 neighbor 已经被访问过
            # 那么应该比较节点 neighbor 和节点 v 的颜色
            # 若相同，则此图不是二分图

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

/* 图遍历框架 */
func traverse(graph Graph, visited []bool, v int) {
	visited[v] = true
    // 遍历节点 v 的所有相邻节点 neighbor
	for _, neighbor := range graph.Neighbors(v) {
		if !visited[neighbor] {
            // 相邻节点 neighbor 没有被访问过
            // 那么应该给节点 neighbor 涂上和节点 v 不同的颜色
			traverse(graph, visited, neighbor)
		} else {
            // 相邻节点 neighbor 已经被访问过
            // 那么应该比较节点 neighbor 和节点 v 的颜色
            // 若相同，则此图不是二分图
            // compare colors between neighbor and v
			// if they are the same, the graph is not bipartite
		}
	}
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

/* 图遍历框架 */
function traverse(graph, visited, v) {
    visited[v] = true;
    // 遍历节点 v 的所有相邻节点 neighbor
    for (let neighbor of graph.neighbors(v)) {
        if (!visited[neighbor]) {
            // 相邻节点 neighbor 没有被访问过
            // 那么应该给节点 neighbor 涂上和节点 v 不同的颜色
            traverse(graph, visited, neighbor);
        } else {
            // 相邻节点 neighbor 已经被访问过
            // 那么应该比较节点 neighbor 和节点 v 的颜色
            // 若相同，则此图不是二分图
        }
    }
}

如果你能看懂上面这段代码，就能写出二分图判定的具体代码了，接下来看两道具体的算法题来实操一下。

题目实践

力扣第 785 题「 判断二分图」就是原题，题目给你输入一个 邻接表 表示一幅无向图，请你判断这幅图是否是二分图。

函数签名如下：

boolean isBipartite(int[][] graph);

比如题目给的例子，输入的邻接表 graph = [[1,2,3],[0,2],[0,1,3],[0,2]]，也就是这样一幅图：

显然无法对节点着色使得每两个相邻节点的颜色都不相同，所以算法返回 false。

但如果输入 graph = [[1,3],[0,2],[1,3],[0,2]]，也就是这样一幅图：

如果把节点 {0, 2} 涂一个颜色，节点 {1, 3} 涂另一个颜色，就可以解决「双色问题」，所以这是一幅二分图，算法返回 true。

结合之前的代码框架，我们可以额外使用一个 color 数组来记录每个节点的颜色，从而写出解法代码：

class Solution {
    // 记录图是否符合二分图性质
    private boolean ok = true;
    // 记录图中节点的颜色，false 和 true 代表两种不同颜色
    private boolean[] color;
    // 记录图中节点是否被访问过
    private boolean[] visited;

    // 主函数，输入邻接表，判断是否是二分图
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        color = new boolean[n];
        visited = new boolean[n];
        // 因为图不一定是联通的，可能存在多个子图
        // 所以要把每个节点都作为起点进行一次遍历
        // 如果发现任何一个子图不是二分图，整幅图都不算二分图
        for (int v = 0; v < n; v++) {
            if (!visited[v]) {
                traverse(graph, v);
            }
        }
        return ok;
    }

    // DFS 遍历框架
    private void traverse(int[][] graph, int v) {
        // 如果已经确定不是二分图了，就不用浪费时间再递归遍历了
        if (!ok) return;

        visited[v] = true;
        for (int w : graph[v]) {
            if (!visited[w]) {
                // 相邻节点 w 没有被访问过
                // 那么应该给节点 w 涂上和节点 v 不同的颜色
                color[w] = !color[v];
                // 继续遍历 w
                traverse(graph, w);
            } else {
                // 相邻节点 w 已经被访问过
                // 根据 v 和 w 的颜色判断是否是二分图
                if (color[w] == color[v]) {
                    // 若相同，则此图不是二分图
                    ok = false;
                    return;
                }
            }
        }
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
private:
    // 记录图是否符合二分图性质
    bool ok = true;
    // 记录图中节点的颜色，false 和 true 代表两种不同颜色
    vector<bool> color;
    // 记录图中节点是否被访问过
    vector<bool> visited;

public:
    // 主函数，输入邻接表，判断是否是二分图
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        color.resize(n);
        visited.resize(n);
        // 因为图不一定是联通的，可能存在多个子图
        // 所以要把每个节点都作为起点进行一次遍历
        // 如果发现任何一个子图不是二分图，整幅图都不算二分图
        for (int v = 0; v < n; v++) {
            if (!visited[v]) {
                traverse(graph, v);
            }
        }
        return ok;
    }

    // DFS 遍历框架
    void traverse(vector<vector<int>>& graph, int v) {
        // 如果已经确定不是二分图了，就不用浪费时间再递归遍历了
        if (!ok) return;

        visited[v] = true;
        for (int w : graph[v]) {
            if (!visited[w]) {
                // 相邻节点 w 没有被访问过
                // 那么应该给节点 w 涂上和节点 v 不同的颜色
                color[w] = !color[v];
                // 继续遍历 w
                traverse(graph, w);
            } else {
                // 相邻节点 w 已经被访问过
                // 根据 v 和 w 的颜色判断是否是二分图
                if (color[w] == color[v]) {
                    // 若相同，则此图不是二分图
                    ok = false;
                    return;
                }
            }
        }
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution:
    def __init__(self):
        # 记录图是否符合二分图性质
        self.ok = True
        # 记录图中节点的颜色，False和True代表两种不同颜色
        self.color = []
        # 记录图中节点是否被访问过
        self.visited = []

    # 主函数，输入邻接表，判断是否是二分图
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        self.color = [False] * n
        self.visited = [False] * n
        # 因为图不一定是联通的，可能存在多个子图
        # 所以要把每个节点都作为起点进行一次遍历
        # 如果发现任何一个子图不是二分图，整幅图都不算二分图
        for v in range(n):
            if not self.visited[v]:
                self.traverse(graph, v)
                if not self.ok:
                    break
        return self.ok

    # DFS 遍历框架
    def traverse(self, graph: List[List[int]], v: int) -> None:
        # 如果已经确定不是二分图了，就不用浪费时间再递归遍历了
        if not self.ok:
            return

        self.visited[v] = True
        for w in graph[v]:
            if not self.visited[w]:
                # 相邻节点 w 没有被访问过
                # 那么应该给节点 w 涂上和节点 v 不同的颜色
                self.color[w] = not self.color[v]
                # 继续遍历 w
                self.traverse(graph, w)
            else:
                # 相邻节点 w 已经被访问过
                # 根据 v 和 w 的颜色判断是否是二分图
                if self.color[w] == self.color[v]:
                    # 若相同，则此图不是二分图
                    self.ok = False
                    return

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func isBipartite(graph [][]int) bool {
    // 记录图是否符合二分图性质
    ok := true
    // 记录图中节点的颜色，false 和 true 代表两种不同颜色
    color := make([]bool, len(graph))
    // 记录图中节点是否被访问过
    visited := make([]bool, len(graph))

    // 因为图不一定是联通的，可能存在多个子图
    // 所以要把每个节点都作为起点进行一次遍历
    // 如果发现任何一个子图不是二分图，整幅图都不算二分图
    for v := 0; v < len(graph); v++ {
        if !visited[v] {
            traverse(graph, v, visited, color, &ok)
        }
    }
    return ok
}

// DFS 遍历框架
func traverse(graph [][]int, v int, visited []bool, color []bool, ok *bool) {
    // 如果已经确定不是二分图了，就不用浪费时间再递归遍历了
    if !*ok {
        return
    }

    visited[v] = true
    for _, w := range graph[v] {
        if !visited[w] {
            // 相邻节点 w 没有被访问过
            // 那么应该给节点 w 涂上和节点 v 不同的颜色
            color[w] = !color[v]
            // 继续遍历 w
            traverse(graph, w, visited, color, ok)
        } else {
            // 相邻节点 w 已经被访问过
            // 根据 v 和 w 的颜色判断是否是二分图
            if color[w] == color[v] {
                // 若相同，则此图不是二分图
                *ok = false
                return
            }
        }
    }
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

/**
 * 记录图是否符合二分图性质
 * false 和 true 代表两种不同颜色
 */
var color;
/**
 * 记录图中节点是否被访问过
 */
var visited;

/**
 * 主函数，输入邻接表，判断是否是二分图
 * @param {number[][]} graph 邻接表
 * @return {boolean} 是否是二分图
 */
var isBipartite = function(graph) {
    var ok = true;
    var n = graph.length;
    color = new Array(n).fill(false);
    visited = new Array(n).fill(false);
    
    /**
     * DFS 遍历框架
     * @param {number[][]} graph 邻接表
     * @param {number} v 当前节点
     */
    var traverse = function(graph, v) {
        // 如果已经确定不是二分图了，就不用浪费时间再递归遍历了
        if (!ok) return;
        
        visited[v] = true;
        var adjNodes = graph[v];
        var numNodes = adjNodes.length;
        for (var i = 0; i < numNodes; i++) {
            var w = adjNodes[i];
            if (!visited[w]) {
                // 相邻节点 w 没有被访问过
                // 那么应该给节点 w 涂上和节点 v 不同的颜色
                color[w] = !color[v];
                // 继续遍历 w
                traverse(graph, w);
            } else {
                // 相邻节点 w 已经被访问过
                // 根据 v 和 w 的颜色判断是否是二分图
                if (color[w] == color[v]) {
                    // 若相同，则此图不是二分图
                    ok = false;
                    return;
                }
            }
        }
    };
    
    // 因为图不一定是联通的，可能存在多个子图
    // 所以要把每个节点都作为起点进行一次遍历
    // 如果发现任何一个子图不是二分图，整幅图都不算二分图
    for (var v = 0; v < n; v++) {
        if (!visited[v]) {
            traverse(graph, v);
        }
    }
    
    return ok;
};
🌟 代码可视化动画 🌟

这就是解决「双色问题」的代码，如果能成功对整幅图染色，则说明这是一幅二分图，否则就不是二分图。

接下来看一下 BFS 算法的逻辑：

class Solution {
    // 记录图是否符合二分图性质
    private boolean ok = true;
    // 记录图中节点的颜色，false 和 true 代表两种不同颜色
    private boolean[] color;
    // 记录图中节点是否被访问过
    private boolean[] visited;

    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        color =  new boolean[n];
        visited =  new boolean[n];
        
        for (int v = 0; v < n; v++) {
            if (!visited[v]) {
                // 改为使用 BFS 函数
                bfs(graph, v);
            }
        }
        
        return ok;
    }

    // 从 start 节点开始进行 BFS 遍历
    private void bfs(int[][] graph, int start) {
        Queue<Integer> q = new LinkedList<>();
        visited[start] = true;
        q.offer(start);
        
        while (!q.isEmpty() && ok) {
            int v = q.poll();
            // 从节点 v 向所有相邻节点扩散
            for (int w : graph[v]) {
                if (!visited[w]) {
                    // 相邻节点 w 没有被访问过
                    // 那么应该给节点 w 涂上和节点 v 不同的颜色
                    color[w] = !color[v];
                    // 标记 w 节点，并放入队列
                    visited[w] = true;
                    q.offer(w);
                } else {
                    // 相邻节点 w 已经被访问过
                    // 根据 v 和 w 的颜色判断是否是二分图
                    if (color[w] == color[v]) {
                        // 若相同，则此图不是二分图
                        ok = false;
                        return;
                    }
                }
            }
        }
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
    // 记录图是否符合二分图性质
    private:
        bool ok = true;
        // 记录图中节点的颜色，false 和 true 代表两种不同颜色
        bool color[100];
        // 记录图中节点是否被访问过
        bool visited[100];
    
    public:
        bool isBipartite(vector<vector<int>>& graph) {
            int n = graph.size();        
            memset(color, 0, sizeof(color));
            memset(visited, 0, sizeof(visited));
            
            for (int v = 0; v < n; v++) {
                if (!visited[v]) {
                    // 改为使用 BFS 函数
                    bfs(graph, v);
                }
            }
            
            return ok;
        }

    // 从 start 节点开始进行 BFS 遍历
    private: 
        void bfs(vector<vector<int>>& graph, int start) {
            queue<int> q;
            visited[start] = true;
            q.push(start);
            
            while (!q.empty() && ok) {
                int v = q.front();
                q.pop();
                // 从节点 v 向所有相邻节点扩散
                for (int i = 0; i < graph[v].size(); i++) {
                    int w = graph[v][i];
                    if (!visited[w]) {
                        // 相邻节点 w 没有被访问过
                        // 那么应该给节点 w 涂上和节点 v 不同的颜色
                        color[w] = !color[v];
                        // 标记 w 节点，并放入队列
                        visited[w] = true;
                        q.push(w);
                    } else {
                        // 相邻节点 w 已经被访问过
                        // 根据 v 和 w 的颜色判断是否是二分图
                        if (color[w] == color[v]) {
                            // 若相同，则此图不是二分图
                            ok = false;
                            return;
                        }
                    }
                }
            }
        }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List
from queue import Queue


class Solution:
    # 记录图是否符合二分图性质
    ok = True
    # 记录图中节点的颜色，False 和 True 代表两种不同颜色
    color = [] 
    # 记录图中节点是否被访问过
    visited = []

    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        self.color = [False] * n
        self.visited = [False] * n

        def bfs(graph, start):
            # 引用闭包变量 ok
            nonlocal ok
            q = Queue()
            q.put(start)
            self.visited[start] = True

            while not q.empty() and ok:
                v = q.get()
                for w in graph[v]:
                    if not self.visited[w]:
                        # 相邻节点 w 没有被访问过
                        # 那么应该给节点 w 涂上和节点 v 不同的颜色
                        self.color[w] = not self.color[v]
                        # 标记 w 节点，并放入队列
                        self.visited[w] = True
                        q.put(w)
                    else:
                        # 相邻节点 w 已经被访问过
                        # 根据 v 和 w 的颜色判断是否是二分图
                        if self.color[w] == self.color[v]:
                            # 若相同，则此图不是二分图
                            ok = False
                            return

        for v in range(n):
            if not self.visited[v]:
                bfs(graph, v)

        return self.ok

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func isBipartite(graph [][]int) bool {
    n := len(graph)
    // 记录图中节点的颜色，false 和 true 代表两种不同颜色
    color := make([]bool, n)
    // 记录图中节点是否被访问过
    visited := make([]bool, n)
    // 记录图是否符合二分图性质
    ok := true

    for v := 0; v < n; v++ {
        if !visited[v] {
            bfs(graph, v, visited, color, &ok)
        }
    }

    return ok
}

// 从 start 节点开始进行 BFS 遍历
func bfs(graph [][]int, start int, visited []bool, color []bool, ok *bool) {
    queue := make([]int, 0)
    visited[start] = true
    queue = append(queue, start)

    for len(queue) > 0 && *ok {
        v := queue[0]
        queue = queue[1:]

        // 从节点 v 向所有相邻节点扩散
        for _, w := range graph[v] {
            if !visited[w] {
                // 相邻节点 w 没有被访问过
                // 那么应该给节点 w 涂上和节点 v 不同的颜色
                color[w] = !color[v]
                // 标记 w 节点，并放入队列
                visited[w] = true
                queue = append(queue, w)
            } else if color[w] == color[v] {
                // 相邻节点 w 已经被访问过
                // 根据 v 和 w 的颜色判断是否是二分图
                if color[w] == color[v] {
                    // 若相同，则此图不是二分图
                    *ok = false
                    return
                }
            }
        }
    }
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var isBipartite = function(graph) {
    // 记录图是否符合二分图性质
    let ok = true;
    // 记录图中节点的颜色，false 和 true 代表两种不同颜色
    let color = new Array(graph.length).fill(false);
    // 记录图中节点是否被访问过
    let visited = new Array(graph.length).fill(false);
    
    // 从 start 节点开始进行 BFS 遍历
    const bfs = (start) => {
        let q = [];
        visited[start] = true;
        q.push(start);
        
        while (q.length > 0 && ok) {
            let v = q.shift();
            // 从节点 v 向所有相邻节点扩散
            for (let i = 0; i < graph[v].length; i++) {
                let w = graph[v][i];
                if (!visited[w]) {
                    // 相邻节点 w 没有被访问过
                    // 那么应该给节点 w 涂上和节点 v 不同的颜色
                    color[w] = !color[v];
                    // 标记 w 节点，并放入队列
                    visited[w] = true;
                    q.push(w);
                } else if (color[w] == color[v]) {
                    // 相邻节点 w 已经被访问过
                    // 根据 v 和 w 的颜色判断是否是二分图
                    if (color[w] == color[v]) {
                        // 若相同，则此图不是二分图
                        ok = false;
                        return;
                    }
                }
            }
        }
    }
    
    let n = graph.length;
    color =  new Array(n).fill(false);
    visited =  new Array(n).fill(false);
        
    for (let v = 0; v < n; v++) {
        if (!visited[v]) {
            // 改为使用 BFS 函数
            bfs(v);
        }
    }
        
    return ok;
};

核心逻辑和刚才实现的 traverse 函数（DFS 算法）完全一样，也是根据相邻节点 v 和 w 的颜色来进行判断的。关于 BFS 算法框架的探讨，详见前文 BFS 算法框架 和 Dijkstra 算法模板，这里就不展开了。

最后再来看看力扣第 886 题「 可能的二分法」：

函数签名如下：

boolean possibleBipartition(int n, int[][] dislikes);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

bool possibleBipartition(int n, vector<vector<int>>& dislikes);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def possibleBipartition(n: int, dislikes: List[List[int]]) -> bool:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func possibleBipartition(n int, dislikes [][]int) bool {}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var possibleBipartition = function(n, dislikes) {
  // Function code here
}

其实这题考察的就是二分图的判定：

如果你把每个人看做图中的节点，相互讨厌的关系看做图中的边，那么 dislikes 数组就可以构成一幅图；

又因为题目说互相讨厌的人不能放在同一组里，相当于图中的所有相邻节点都要放进两个不同的组；

那就回到了「双色问题」，如果能够用两种颜色着色所有节点，且相邻节点颜色都不同，那么你按照颜色把这些节点分成两组不就行了嘛。

所以解法就出来了，我们把 dislikes 构造成一幅图，然后执行二分图的判定算法即可：

class Solution {
    private boolean ok = true;
    private boolean[] color;
    private boolean[] visited;

    public boolean possibleBipartition(int n, int[][] dislikes) {
        // 图节点编号从 1 开始
        color = new boolean[n + 1];
        visited = new boolean[n + 1];
        // 转化成邻接表表示图结构
        List<Integer>[] graph = buildGraph(n, dislikes);
        
        for (int v = 1; v <= n; v++) {
            if (!visited[v]) {
                traverse(graph, v);
            }
        }
        
        return ok;
    }

    // 建图函数
    private List<Integer>[] buildGraph(int n, int[][] dislikes) {
        // 图节点编号为 1...n
        List<Integer>[] graph = new LinkedList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] edge : dislikes) {
            int v = edge[1];
            int w = edge[0];
            // 「无向图」相当于「双向图」
            // v -> w
            graph[v].add(w);
            // w -> v
            graph[w].add(v);
        }
        return graph;
    }

    // 和之前的 traverse 函数完全相同
    private void traverse(List<Integer>[] graph, int v) {
        if (!ok) return;
        visited[v] = true;
        for (int w : graph[v]) {
            if (!visited[w]) {
                color[w] = !color[v];
                traverse(graph, w);
            } else {
                if (color[w] == color[v]) {
                    ok = false;
                    return;
                }
            }
        }
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
private:
    bool ok = true;
    vector<bool> color;
    vector<bool> visited;

public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        // 图的节点编号从 1 开始
        color.resize(n + 1);
        visited.resize(n + 1);
        // 转化成邻接表表示图结构
        vector<vector<int>> graph = buildGraph(n, dislikes);

        for (int v = 1; v <= n; v++) {
            if (!visited[v]) {
                traverse(graph, v);
            }
        }

        return ok;
    }

    // 建图函数
    vector<vector<int>> buildGraph(int n, vector<vector<int>>& dislikes) {
        // 图的节点编号为 1...n
        vector<vector<int>> graph(n + 1);
        for (int i = 1; i <= n; i++) {
            graph[i] = {};
        }
        for (auto edge : dislikes) {
            int v = edge[1];
            int w = edge[0];
            // 「无向图」相当于「双向图」
            // v -> w
            graph[v].push_back(w);
            // w -> v
            graph[w].push_back(v);
        }
        return graph;
    }

    // 和之前的 traverse 函数完全相同
    void traverse(vector<vector<int>>& graph, int v) {
        if (!ok) return;
        visited[v] = true;
        for (int w : graph[v]) {
            if (!visited[w]) {
                color[w] = !color[v];
                traverse(graph, w);
            } else {
                if (color[w] == color[v]) {
                    ok = false;
                    return;
                }
            }
        }
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

class Solution:
    def __init__(self):
        self.ok = True
        self.color = []
        self.visited = []

    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        self.color = [False] * (n+1)
        self.visited = [False] * (n+1)
        graph = self.buildGraph(n, dislikes)
        
        for v in range(1, n+1):
            if not self.visited[v]:
                self.traverse(graph, v)
        
        return self.ok

    def buildGraph(self, n: int, dislikes: List[List[int]]) -> List[List[int]]:
        graph = [[] for _ in range(n+1)]
        for edge in dislikes:
            v, w = edge[1], edge[0]
            # 「无向图」相当于「双向图」
            # v -> w
            graph[v].append(w)
            # w -> v
            graph[w].append(v)
        return graph

    def traverse(self, graph: List[List[int]], v: int) -> None:
        if not self.ok:
            return
        self.visited[v] = True
        for w in graph[v]:
            if not self.visited[w]:
                self.color[w] = not self.color[v]
                self.traverse(graph, w)
            else:
                if self.color[w] == self.color[v]:
                    self.ok = False
                    return

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func possibleBipartition(n int, dislikes [][]int) bool {
    ok := true
    color := make([]bool, n+1)
    visited := make([]bool, n+1)
    graph := buildGraph(n, dislikes)

    for v := 1; v <= n; v++ {
        if !visited[v] {
            traverse(&graph, v, &visited, &color, &ok)
        }
    }

    return ok
}

// 建图函数
func buildGraph(n int, dislikes [][]int) [][]int {
    graph := make([][]int, n+1)
    for i := 1; i <= n; i++ {
        graph[i] = make([]int, 0)
    }

    for _, edge := range dislikes {
        v := edge[1]
        w := edge[0]

        graph[v] = append(graph[v], w)
        graph[w] = append(graph[w], v)
    }

    return graph
}

// 和之前的 traverse 函数完全相同
func traverse(graph *[][]int, v int, visited *[]bool, color *[]bool, ok *bool) {
    if !*ok {
        return
    }
    (*visited)[v] = true
    for _, w := range (*graph)[v] {
        if !(*visited)[w] {
            (*color)[w] = !(*color)[v]
            traverse(graph, w, visited, color, ok)
        } else {
            if (*color)[w] == (*color)[v] {
                *ok = false
                return
            }
        }
    }
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

/**
 * @param {number} n
 * @param {number[][]} dislikes
 * @return {boolean}
 */

var possibleBipartition = function(n, dislikes) {
    var ok = true;
    var color = [];
    var visited = [];

    /**
     * 建图函数
     * @param {number} n
     * @param {number[][]} dislikes
     * @return {Array.<number[]>}
     */
    var buildGraph = function(n, dislikes) {
        var graph = new Array(n + 1).fill(null).map(() => []);
        for (var i = 0; i < dislikes.length; i++) {
            var v = dislikes[i][1];
            var w = dislikes[i][0];

            // 「无向图」相当于「双向图」
            // v -> w
            graph[v].push(w);
            // w -> v
            graph[w].push(v);
        }
        return graph;
    }

    /**
     * 深度优先搜索遍历
     * @param {Array.<number[]>} graph
     * @param {number} v
     */
    var traverse = function(graph, v) {
        if (!ok) return;

        visited[v] = true;
        for (var i = 0; i < graph[v].length; i++) {
            var w = graph[v][i];

            if (!visited[w]) {
                color[w] = !color[v];
                traverse(graph, w);
            } else {
                if (color[w] == color[v]) {
                    ok = false;
                    return;
                }
            }
        }
    }

    color = new Array(n + 1);
    visited = new Array(n + 1);

    var graph = buildGraph(n, dislikes);

    for (var v = 1; v <= n; v++) {
        if (!visited[v]) {
            traverse(graph, v);
        }
    }

    return ok;
};
🌟 代码可视化动画 🌟

至此，这道题也使用 DFS 算法解决了，如果你想用 BFS 算法，和之前写的解法是完全一样的，可以自己尝试实现。

二分图的判定算法就讲到这里，更多二分图的高级算法，敬请期待。

引用本文的文章

＿＿＿＿＿＿＿＿＿＿＿＿＿

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释