深入浅出二分图检测：从原理到代码实现

在图论的广阔天地中，二分图 是一个非常有趣且实用的概念。作为一名开发者，你可能在解决“图着色问题”或者在处理社交网络、资源分配等场景时遇到过它。简单来说，二分图就像是将图中的节点分成两个互不往来的“派系”，所有的边都只能连接这两个派系之间，而派系内部没有边。

在这篇文章中，我们将一起深入探讨如何判断一个给定的图是否是二分图。我们将从最基础的定义出发，利用 广度优先搜索 (BFS) 和 深度优先搜索 (DFS) 两种核心算法来解决这个问题，并通过实际的代码示例让你彻底掌握这一技能。你还会了解到处理非连通图、自环边以及平行边的最佳实践。让我们开始吧！

什么是二分图？

首先，我们需要明确什么是二分图。所谓的 二分图，是指我们可以将图的所有顶点集划分为两个不相交的集合（通常我们称之为集合 U 和集合 V），使得图中的每一条边都连接一个 U 中的顶点和一个 V 中的顶点。

换句话说，同一个集合内的顶点之间不能有边相连。这个定义听起来有点抽象，但其实它和一个经典的游戏问题紧密相关——图着色问题。如果我们只用两种颜色（比如红色和蓝色）来给图涂色，要求相邻的两个节点颜色必须不同，那么能成功涂色的图就是二分图。这通常被称为“2-着色”问题。

#### 判断核心：没有奇数环

有一个重要的性质我们需要记住：一个图是二分图，当且仅当它不包含奇数长度的环（奇环）。

为什么？想象一下，如果你沿着一个环走，为了满足“相邻节点颜色不同”的条件，你必须在两种颜色之间来回切换。如果你走了奇数步回到了起点，你会发现起点原本的颜色和你现在需要的颜色冲突了。因此，只要图中存在奇数环，它就不是二分图。

算法思路

为了检测一个图是否满足这个条件，我们可以采用 图遍历算法。思路非常直观：我们尝试用两种颜色（比如 0 和 1）对整个图进行着色。从任意一个未着色的节点开始，给它赋予颜色 0，然后遍历它的所有邻居，将邻居染成颜色 1。接着继续遍历邻居的邻居，将它们染回颜色 0，以此类推。

在这个过程中，如果我们发现一个已经被着色的邻居节点，它的颜色竟然和当前节点相同，那么我们就碰到了冲突，说明这个图不是二分图。如果整个遍历过程结束都没有发生冲突，那么恭喜，这就是一个二分图。

我们需要特别注意非连通图的情况。一个图可能由几个互不相连的部分组成，我们必须确保对每一个连通分量都进行检查，只要有任何一个分量不是二分图，整个图就不是。

接下来，让我们看看具体的代码实现。我们将分别使用广度优先搜索 (BFS) 和深度优先搜索 (DFS) 来解决这个问题。

方法一：使用广度优先搜索 (BFS)

BFS 是解决这个问题最自然的选择，因为它是逐层遍历的。我们很容易将“层级”与“颜色”对应起来：奇数层一种颜色，偶数层一种颜色。

#### 算法步骤

• 初始化：创建一个颜色数组（或者叫染色数组），初始值设为 -1，表示所有节点都未被着色。
• 遍历所有节点：我们需要一个循环来处理图中的每一个节点。这主要是为了处理非连通图的情况。如果节点未被着色，我们就从这里开始一次新的 BFS。
• 开始 BFS：将当前节点标记为颜色 0，并放入队列。
• 处理队列：只要队列不为空，就弹出队首元素。遍历它的所有邻居节点：

* 如果邻居未被着色（颜色为 -1），将其染成与当前节点相反的颜色（1 - 当前颜色），并加入队列。

* 如果邻居已经被着色，且颜色与当前节点相同，则直接返回 false（不是二分图）。

• 完成检测：如果所有节点都处理完毕且没有发生冲突，返回 true。

#### 代码实现 (C++)

让我们来看看如何用 C++ 优雅地实现这个逻辑。这里我们使用邻接表来存储图结构。

#include 
#include 
#include 

using namespace std;

// 辅助函数：构建图的邻接表
// 输入：顶点数 V 和边列表 edges
vector<vector> constructAdjacencyList(int V, vector<vector>& edges) {
    vector<vector> adj(V);
    for (auto& edge : edges) {
        int u = edge[0];
        int v = edge[1];
        // 因为是无向图，所以要添加双向连接
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    return adj;
}

// 主函数：判断图是否为二分图
bool isBipartiteBFS(int V, vector<vector>& edges) {
    // 1. 构建邻接表
    vector<vector> adj = constructAdjacencyList(V, edges);

    // 2. 初始化颜色数组，-1 表示未着色
    // 我们可以用 0 和 1 代表两种不同的颜色
    vector color(V, -1);

    queue q;

    // 3. 遍历所有顶点（处理非连通图）
    for (int i = 0; i < V; ++i) {
        // 如果当前节点未被着色，说明这是一个新的连通分量，需要开始新的 BFS
        if (color[i] == -1) {
            // 起始节点染成颜色 0
            color[i] = 0;
            q.push(i);

            // 开始 BFS 循环
            while (!q.empty()) {
                int u = q.front();
                q.pop();

                // 检查所有邻居
                for (int v : adj[u]) {
                    // 情况 A: 邻居未着色
                    if (color[v] == -1) {
                        // 将邻居染成相反的颜色
                        color[v] = 1 - color[u];
                        q.push(v);
                    }
                    // 情况 B: 邻居已着色，检查颜色是否冲突
                    else if (color[v] == color[u]) {
                        // 如果颜色相同，说明不是二分图
                        return false;
                    }
                }
            }
        }
    }

    // 如果所有分量都检查通过，则是二分图
    return true;
}

int main() {
    // 测试用例 1: 包含奇数环，不是二分图
    int V1 = 4;
    vector<vector> edges1 = {{0, 1}, {1, 2}, {2, 0}, {2, 3}};
    
    cout << "Test Case 1 (Non-Bipartite): " << (isBipartiteBFS(V1, edges1) ? "true" : "false") << endl;

    // 测试用例 2: 简单的链，是二分图
    int V2 = 4;
    vector<vector> edges2 = {{0, 1}, {1, 2}, {2, 3}};

    cout << "Test Case 2 (Bipartite): " << (isBipartiteBFS(V2, edges2) ? "true" : "false") << endl;

    return 0;
}

方法二：使用深度优先搜索 (DFS)

除了 BFS，我们还可以使用 深度优先搜索 (DFS)。DFS 的思路也是一样的：尝试着色，遇到冲突就返回。不过 DFS 是通过递归（或栈）来实现的，它会沿着一条路径一直走到底，这有时候在代码实现上会显得更加简洁。

#### 算法逻辑

对于每一个节点，我们执行以下操作：

• 如果当前节点未被着色，先给它一个初始颜色（比如 0）。
• 遍历当前节点的所有邻居。
• 对于每一个邻居：

* 如果它没被着色，我们递归调用 DFS 函数，试图将它染成相反的颜色。如果递归返回 INLINECODEd3c35786，说明后续检测出了问题，我们直接向上传递 INLINECODE2c7bffca。

* 如果它已经被着色，检查它的颜色是否和当前节点颜色相同。如果相同，返回 false。

• 如果当前节点的所有邻居都处理完毕且没有冲突，返回 true。

#### 代码实现 (C++)

下面是使用递归 DFS 的实现方式。注意看我们如何巧妙地处理颜色的翻转（1 - color）。

#include 
#include 

using namespace std;

// 辅助函数：构建邻接表
vector<vector> constructAdjacencyList(int V, vector<vector>& edges) {
    vector<vector> adj(V);
    for (auto& edge : edges) {
        adj[edge[0]].push_back(edge[1]);
        adj[edge[1]].push_back(edge[0]);
    }
    return adj;
}

// DFS 检测函数（递归部分）
// u: 当前节点
// c: 当前节点的颜色
bool dfsCheck(int u, int c, vector<vector>& adj, vector& color) {
    // 将当前节点染上颜色 c
    color[u] = c;

    // 遍历所有邻居
    for (int v : adj[u]) {
        // 如果邻居未被着色
        if (color[v] == -1) {
            // 递归调用：将邻居染成相反的颜色 (1 - c)
            // 如果递归结果为 false，说明后续检测失败
            if (!dfsCheck(v, 1 - c, adj, color)) {
                return false;
            }
        }
        // 如果邻居已被着色，且颜色与当前节点相同，发生冲突
        else if (color[v] == c) {
            return false;
        }
    }
    // 当前节点及其子节点都正常
    return true;
}

// 主函数：判断图是否为二分图
bool isBipartiteDFS(int V, vector<vector>& edges) {
    vector<vector> adj = constructAdjacencyList(V, edges);
    vector color(V, -1);

    // 遍历所有节点，处理非连通图
    for (int i = 0; i < V; ++i) {
        // 如果节点未着色，从该节点开始 DFS
        // 默认从颜色 0 开始
        if (color[i] == -1) {
            if (!dfsCheck(i, 0, adj, color)) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    int V = 5;
    // 测试用例 3: 一个较大的二分图
    // 0-1-2-3 构成一条链，4 是孤立的
    vector<vector> edges3 = {{0, 1}, {1, 2}, {2, 3}};

    cout << "Test Case 3 (DFS - Bipartite): " << (isBipartiteDFS(V, edges3) ? "true" : "false") << endl;

    return 0;
}

代码实现 (Java 版本)

为了照顾习惯使用 Java 的开发者，我也准备了一个完整的 Java 实现。这里我们使用 ArrayList 来存储邻接表，并使用队列来实现 BFS 逻辑。

import java.util.*;

public class BipartiteCheck {
    
    // 辅助方法：构建邻接表
    public static List<List> constructAdjacencyList(int V, int[][] edges) {
        List<List> adj = new ArrayList();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList());
        }
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        return adj;
    }

    // BFS 方法检查二分图
    public static boolean isBipartiteBFS(int V, int[][] edges) {
        List<List> adj = constructAdjacencyList(V, edges);
        int[] color = new int[V];
        Arrays.fill(color, -1); // -1 表示未着色

        Queue q = new LinkedList();

        for (int i = 0; i < V; i++) {
            if (color[i] == -1) {
                color[i] = 0;
                q.add(i);

                while (!q.isEmpty()) {
                    int u = q.poll();

                    for (int v : adj.get(u)) {
                        if (color[v] == -1) {
                            color[v] = 1 - color[u];
                            q.add(v);
                        } else if (color[v] == color[u]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int V = 4;
        int[][] edges = {{0, 1}, {0, 2}, {1, 2}, {2, 3}}; // 包含三角形 0-1-2

        // 输出: false (因为存在奇数环)
        System.out.println("Is Bipartite: " + isBipartiteBFS(V, edges));
    }
}

实际应用与性能分析

掌握这个算法不仅仅是为了应付面试。在实际的工程中，二分图检测有很多应用场景：

• 资源分配：例如，将任务分配给工人，如果某些任务不能由同一个人完成（即有冲突），我们可以将任务和人建模成二分图来判断是否存在完美匹配或合理的分配方案。
• 社交网络：检测网络中是否存在两个对立的派系（例如政治倾向预测）。

#### 时间复杂度与空间复杂度

让我们来看看这两个算法的效率如何。

• 时间复杂度：O(V + E)。无论 BFS 还是 DFS，我们实际上都只是遍历了图中的每一个节点（V）和每一条边（E）各一次。这是处理图问题的标准线性复杂度，非常高效。
• 空间复杂度：O(V)。我们需要一个额外的数组 color 来存储颜色信息。此外，BFS 需要一个队列，最坏情况下（例如星型图）队列中可能存储 O(V) 个节点；DFS 需要递归栈空间，最坏情况下也是 O(V)。邻接表本身的空间不算在内的话，辅助空间是 O(V)。

常见错误与调试技巧

在处理这类问题时，你可能会遇到一些常见的陷阱，让我们来看看如何避免它们：

• 忽略了非连通图：这是最容易犯的错误。如果你只从节点 0 开始 BFS，那么如果图中有另一部分与节点 0 不连通，你就漏掉了那部分图的检测。必须要有一个外层循环遍历所有节点。
• 自环边：如果输入包含 INLINECODEf03f5149，即节点连向自己，这肯定不是二分图（因为在同一个集合内部连了一条边）。虽然我们的邻接表构建逻辑通常能处理，但在构建图之前专门检查一下 INLINECODE1311bbda 的边能提前终止算法，是一个很好的优化。
• 平行边：如果输入中有两条完全相同的边 [0, 1] 出现两次，我们的逻辑依然适用，因为第一次访问时会给邻居上色，第二次访问时只会检查颜色，不会造成死循环或逻辑错误。

总结

在这篇文章中，我们详细探讨了如何检测一个图是否为二分图。我们了解到，这本质上是一个 图着色问题，核心在于使用两种颜色对图进行着色，确保相邻节点颜色不同。

我们通过 BFS（逐层遍历）和 DFS（递归深入）两种方法实现了这一逻辑，并提供了完整的 C++ 和 Java 代码示例。这两种方法在时间和空间复杂度上都是线性的 O(V + E)，是目前解决此类问题的最优解法。

接下来，当你遇到类似“节点分组”、“冲突检测”或者“图着色”的问题时，不妨停下来想一想：这是否是一个二分图检测问题？试着画出模型，应用我们今天学到的算法，相信你能迎刃而解！

希望这篇文章能帮助你加深对图算法的理解。如果你想继续挑战更难的问题，可以尝试学习 最大二分图匹配 算法，那是另一个经典的算法话题。