基于 DFS 的二分图检测算法

题目描述

给定一个无向图，判断它是否是一个二分图。二分图的定义是：可以将图中的所有顶点分成两个不相交的集合，使得图中任意一条边都连接着两个不同集合中的顶点。换句话说，二分图可以被着色为两种颜色，使得任意相邻的顶点颜色不同。如果图是二分图，输出一种可行的二染色方案；否则，输出它不是二分图。

解题过程

我们将采用深度优先搜索（DFS）来解决这个问题。DFS 能够系统地遍历图中的每个顶点，并在遍历过程中尝试给顶点染色，同时检查是否存在冲突。

步骤 1：理解二分图的等价条件

一个图是二分图，当且仅当它不包含奇数长度的环。在染色过程中，如果我们从一个顶点开始，将其染成一种颜色（例如颜色 0），那么它的所有邻居必须染成另一种颜色（例如颜色 1）。如果在染色过程中，发现某个邻居已经被染色，并且颜色与当前要染的颜色相同，那么就出现了冲突，说明图中存在奇数长度的环，因此不是二分图。

步骤 2：算法设计思路

我们可以从任意一个未访问的顶点开始，进行 DFS 遍历。在 DFS 过程中：

1. 给当前顶点染色。
2. 遍历当前顶点的所有邻居：
   • 如果邻居未访问，则递归访问它，并给它染上与当前顶点不同的颜色。
   • 如果邻居已访问，则检查它的颜色是否与当前顶点不同。如果相同，则发现冲突，图不是二分图。

如果遍历完所有顶点后都没有发现冲突，那么图是二分图。由于图可能不连通，我们需要对每个连通分量都执行一次 DFS。

步骤 3：数据结构与初始化

假设图有 \(n\) 个顶点，编号从 0 到 \(n-1\)，并且以邻接表形式存储（便于快速访问邻居）。
我们需要以下数据结构：

• vector<int> color：长度为 \(n\)，记录每个顶点的颜色。初始化为 -1，表示未访问。颜色用 0 和 1 表示。
• vector<vector<int>> adj：邻接表，存储图的边。

步骤 4：DFS 函数实现

DFS 函数需要以下参数：

• int u：当前访问的顶点。
• int c：要染给顶点 u 的颜色。

在 DFS 函数中：

1. 将 color[u] 设为 c。
2. 对于 u 的每个邻居 v：
   • 如果 color[v] == -1，则递归调用 dfs(v, 1 - c)。如果递归返回 false，则直接返回 false。
   • 如果 color[v] != -1 且 color[v] == c，则发现冲突，返回 false。
3. 如果所有邻居处理完毕都没有冲突，返回 true。

步骤 5：主控制逻辑

由于图可能不连通，我们需要检查每个顶点：

1. 初始化 color 数组为 -1。
2. 对于每个顶点 i：
   • 如果 color[i] == -1，则从它开始进行 DFS，初始颜色设为 0。如果 DFS 返回 false，则整个图不是二分图。
3. 如果所有连通分量都成功染色，则图是二分图。此时 color 数组就是一种二染色方案。

步骤 6：算法复杂度分析

• 时间复杂度：每个顶点和每条边在 DFS 中都会被访问一次，因此时间复杂度是 \(O(n + m)\)，其中 \(n\) 是顶点数，\(m\) 是边数。
• 空间复杂度：存储颜色数组需要 \(O(n)\)，邻接表需要 \(O(n + m)\)，递归栈在最坏情况下可能需要 \(O(n)\) 空间，因此总空间复杂度为 \(O(n + m)\)。

步骤 7：示例演示

考虑一个简单的图，顶点为 0, 1, 2, 3，边为 (0,1), (1,2), (2,3), (3,0)。这是一个四边形（偶数长度环），应该是二分图。

执行过程：

1. 从顶点 0 开始，染颜色 0。
2. 访问邻居 1，染颜色 1。
3. 从 1 访问邻居 2，染颜色 0。
4. 从 2 访问邻居 3，染颜色 1。
5. 检查 3 的邻居 0：已染色，颜色为 0，与 3 的颜色 1 不同，无冲突。
6. 所有顶点访问完毕，无冲突，是二分图。颜色方案：0:0, 1:1, 2:0, 3:1。

再考虑一个三角形图，顶点 0,1,2，边 (0,1), (1,2), (2,0)。这是一个奇数长度环，不是二分图。

执行过程：

1. 从顶点 0 开始，染颜色 0。
2. 访问邻居 1，染颜色 1。
3. 从 1 访问邻居 2，染颜色 0。
4. 检查 2 的邻居 0：已染色，颜色为 0，与 2 的颜色相同，冲突！返回 false。

步骤 8：代码框架（C++风格伪代码）

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

总结

基于 DFS 的二分图检测算法通过递归染色和冲突检查，高效地判断一个图是否为二分图，并能在是二分图时提供一种染色方案。算法的核心思想是模拟二染色过程，并在出现相邻同色时及时检测到奇数环的存在。这种方法直观、易于实现，且具有线性时间复杂度。