二分图（Bipartite Graph）的判定及其应用

一、问题描述

给定一个无向图（可能包含多个连通分量），判断该图是否为二分图（Bipartite Graph）。

• 二分图定义：图中的所有顶点可以被划分到两个互不相交的集合 U 和 V 中，使得图中任意一条边的两个端点分别属于 U 和 V（即同集合内的顶点之间没有边）。
• 等价条件：图可以被二着色（用两种颜色对顶点染色），使得任意相邻顶点颜色不同。若存在奇环（长度为奇数的环），则图不是二分图。

输入形式：通常给定图的顶点数 n 和边列表（如邻接表或邻接矩阵）。
输出：布尔值，表示是否为二分图。

二、理解核心性质

关键结论：
一个图是二分图 ⇔ 图中不存在奇环。

• 偶环（如长度为 4 的环）可以被二着色，但奇环无法用两种颜色交替染色（首尾颜色冲突）。
• 因此，判定二分图等价于检测是否存在奇环。

三、判定方法：染色法（BFS/DFS）

1. 算法思路

• 初始化所有顶点为“未染色”（例如用 0 表示）。
• 遍历每个连通分量（避免非连通图漏判）：
  • 从一个未染色的顶点开始，将其染成颜色 1。
  • 对相邻顶点递归或迭代染色：
    • 若相邻顶点未染色，则染成相反颜色（颜色 2）。
    • 若相邻顶点已染色，且颜色与当前顶点相同，则发现冲突 → 不是二分图。
• 若所有顶点成功染色且无冲突，则是二分图。

2. 步骤详解（以 BFS 为例）

示例图（邻接表表示）：
顶点 0, 1, 2, 3；边： (0,1), (1,2), (2,3), (3,0)
该图是一个长度为 4 的环（偶环），应是二分图。

过程：

1. 初始化颜色数组 color[]，全为 0（未染色）。
2. 遍历每个顶点，对未染色的顶点启动 BFS：
   • 起点为顶点 0，染成 1（入队列）。
   • 队列弹出 0，检查邻居 1 和 3：
     • 邻居 1 未染色 → 染成 -1，入队。
     • 邻居 3 未染色 → 染成 -1，入队。
   • 弹出 1，邻居 0 颜色为 1（与 1 的颜色 -1 不同，合法），邻居 2 未染色 → 染成 1，入队。
   • 弹出 3，邻居 0 颜色 1（与 3 的颜色 -1 不同，合法），邻居 2 颜色 1（与 3 的颜色 -1 不同，合法）。
   • 弹出 2，邻居 1 颜色 -1（合法），邻居 3 颜色 -1（合法）。
3. 未发现冲突，判定为二分图。

时间复杂度：O(V + E)，其中 V 为顶点数，E 为边数（遍历所有顶点和边一次）。

四、代码实现（Python）

from collections import deque

def isBipartite(graph):
    n = len(graph)
    color = [0] * n  # 0: 未染色, 1: 颜色A, -1: 颜色B
    
    for i in range(n):
        if color[i] != 0:
            continue
        # BFS 遍历连通分量
        queue = deque([i])
        color[i] = 1
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if color[neighbor] == 0:
                    color[neighbor] = -color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False
    return True

# 示例：graph 是邻接表形式
graph = [[1,3], [0,2], [1,3], [0,2]]
print(isBipartite(graph))  # True（偶环，是二分图）

graph_with_odd_cycle = [[1,2], [0,2], [0,1]]
print(isBipartite(graph_with_odd_cycle))  # False（三角形奇环）

五、常见变形与扩展

1. DFS 实现：递归染色，逻辑与 BFS 类似。

2. 并查集解法（扩展思路）：

   • 对于每条边 (u, v)，将 u 的所有邻居合并到同一个集合，若发现 u 和 v 在同一集合则冲突。
   • 但需注意实现细节，通常染色法更直观。

3. 二分图匹配问题：

   • 匈牙利算法（Hungarian Algorithm）用于求解二分图最大匹配（如任务分配、婚配问题）。
   • 判定二分图是使用匈牙利算法的前提。

六、典型应用场景

1. 广告投放与用户匹配：用户和广告分为两类，边表示用户可能点击的广告，求最大匹配。
2. 任务调度：工人与任务分为两类，边表示工人能完成的任务，求最大匹配。
3. 社交网络分析：判断网络是否可以划分为两个阵营（如敌友关系）。
4. 电路设计：某些布局问题可抽象为二分图着色。

七、总结要点

• 核心：二分图判定 ⇔ 二染色 ⇔ 无奇环。
• 算法：BFS/DFS 染色，时间复杂度 O(V+E)。
• 注意：非连通图需遍历所有连通分量。
• 扩展：判定后常需进一步求最大匹配（匈牙利算法）。