基于DFS的二分图检测算法

我将为您讲解如何使用深度优先搜索（DFS）来检测一个图是否为二分图。

题目描述
给定一个无向图G=(V,E)，判断该图是否是二分图。二分图是指能够将图中的所有顶点划分为两个不相交的子集U和V，使得图中的每条边都连接U中的一个顶点和V中的一个顶点（即不存在连接同一子集内两个顶点的边）。

算法思路

1. 二分图等价于2-可着色图，即可以用两种颜色给所有顶点着色，使得相邻顶点颜色不同
2. 使用DFS对图进行遍历，同时尝试用两种颜色给顶点着色
3. 如果在着色过程中发现相邻顶点颜色相同，则说明不是二分图

详细解题步骤

步骤1：初始化

• 创建颜色数组color[]，大小为顶点数，初始值为-1（表示未着色）
• 选择两种颜色（通常用0和1表示）

def is_bipartite_dfs(graph):
    n = len(graph)  # 顶点数量
    color = [-1] * n  # 颜色数组，-1表示未着色

步骤2：DFS遍历函数

• 从当前顶点u开始，给它着色为c
• 遍历u的所有邻居顶点v：
  • 如果v未着色，递归调用DFS，尝试给v着色为1-c（相反颜色）
  • 如果递归返回False，说明发现冲突，立即返回False
  • 如果v已着色且颜色与u相同，说明发现冲突，返回False

def dfs(u, c):
    color[u] = c  # 给顶点u着色为c
    
    # 遍历所有邻居
    for v in graph[u]:
        if color[v] == -1:  # 邻居未着色
            if not dfs(v, 1 - c):  # 递归着色，使用相反颜色
                return False
        elif color[v] == color[u]:  # 邻居颜色与当前顶点相同
            return False
    return True

步骤3：处理非连通图

• 图可能由多个连通分量组成，需要确保每个分量都是二分图
• 遍历所有顶点，对每个未访问的顶点启动DFS

for i in range(n):
    if color[i] == -1:  # 发现新的连通分量
        if not dfs(i, 0):  # 从颜色0开始着色
            return False
return True

完整算法代码

def is_bipartite_dfs(graph):
    n = len(graph)
    color = [-1] * n
    
    def dfs(u, c):
        color[u] = c
        for v in graph[u]:
            if color[v] == -1:
                if not dfs(v, 1 - c):
                    return False
            elif color[v] == color[u]:
                return False
        return True
    
    for i in range(n):
        if color[i] == -1:
            if not dfs(i, 0):
                return False
    return True

算法复杂度

• 时间复杂度：O(V+E)，每个顶点和边只被访问一次
• 空间复杂度：O(V)，用于存储颜色数组和递归栈

示例演示

例1：二分图（可以正确着色）

图：0-1-2
    | /
    3

邻接表：
0: [1, 3]
1: [0, 2]
2: [1, 3]
3: [0, 2]

着色过程：
从顶点0开始着色为0
顶点1着色为1，顶点3着色为1
顶点2着色为0
结果：是二分图

例2：非二分图（存在奇环）

图：0-1-2-0（三角形）

邻接表：
0: [1, 2]
1: [0, 2]
2: [0, 1]

着色过程：
顶点0着色为0
顶点1着色为1
顶点2：邻居0颜色0，邻居1颜色1，冲突！
结果：不是二分图

关键要点

1. 二分图的必要条件是图中不包含长度为奇数的环
2. DFS方法可以同时完成遍历和着色检查
3. 必须处理非连通图的情况，检查每个连通分量
4. 算法效率高，适用于大规模图结构