二分图判定算法

labuladong约 10096 字大约 34 分钟数据结构图论算法

Info

数据结构精品课open in new window 和递归算法专题课open in new window 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》open in new window 出版，签名版限时半价！

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

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

Tip

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

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

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

二分图简介

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

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

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

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

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

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

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

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

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

既然是存储映射关系，最简单的不就是使用哈希表嘛，我们可以使用一个 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 题「判断二分图open in new window」就是原题，题目给你输入一个邻接表表示一幅无向图，请你判断这幅图是否是二分图。

函数签名如下：

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 题「可能的二分法open in new window」：

函数签名如下：

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 算法，和之前写的解法是完全一样的，可以自己尝试实现。

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

引用本文的文章

Kruskal 最小生成树算法 Prim 最小生成树算法图论基础及遍历算法并查集（Union-Find）算法我的刷题心得环检测及拓扑排序算法用算法打败算法

引用本文的题目

安装我的 Chrome 刷题插件open in new window 点开下列题目可直接查看解题思路：

LeetCode	力扣
310. Minimum Height Treesopen in new window	310. 最小高度树open in new window

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

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

# 二分图简介

# 二分图判定思路

# 题目实践

二分图简介

二分图判定思路

题目实践