数据结构与算法 / 系统课时

二分图怎样用染色判断

二分图怎样用染色判断

判断一个图是不是二分图,可以转化成一个非常直接的约束:相邻顶点必须使用不同颜色。沿着边不断给顶点交替染成两种颜色,如果某条边最终连接了两个同色顶点,就说明图中存在无法满足二分要求的结构。

学习目标

  • 理解二分图、两色染色与奇环之间的等价关系
  • 掌握使用 BFS 和 DFS 完成二分图判断的方法
  • 正确处理非连通图、自环和染色冲突等边界情况

两色染色为什么能够判断二分图

二分图要求把全部顶点分成两个集合,同一集合内部没有边。因此可以把两个集合分别看成颜色 0 和颜色 1:一条边的两个端点必须颜色不同。

从一个未染色顶点出发,先把它染成 0;访问它的邻居时统一染成 1;再访问下一层时重新染成 0。只要这个过程始终没有冲突,最终所有已访问顶点就形成了一组合法的二分划分。

如果遇到一条边,其两个端点已经被染成相同颜色,就不能通过重新选择起始颜色解决。把整个连通分量的两种颜色整体互换,冲突仍然存在。这种冲突正对应图中出现了奇数长度的环。

两色染色成功与奇环冲突对比

BFS 和 DFS 的判断过程

BFS 使用队列按层扩展,非常符合“相邻层颜色交替”的直觉。每取出一个顶点,就检查它的全部邻居:未染色就赋予相反颜色,已经染色则检查是否与当前顶点同色。

DFS 的约束完全相同,只是访问顺序改成沿一条路径深入。无论递归还是显式栈,只要第一次访问顶点时记录颜色,并在遇到已染色邻居时检查冲突,最终判断结果都与 BFS 一致。

对于非连通图,只从一个顶点搜索是不够的。必须遍历所有顶点,每遇到一个尚未染色的顶点,就从它启动一次新的 BFS 或 DFS。只要任意一个连通分量出现冲突,整张图就不是二分图。

用代码实现两种染色方式

下面使用邻接表表示无向图。第一个图由一个四边形和一条独立边组成,可以正常两色染色;第二个图是三角形,其中存在奇环,因此会产生冲突。

python
from collections import deque


def is_bipartite_bfs(graph):
    color = {}

    for start in graph:
        if start in color:
            continue

        color[start] = 0
        queue = deque([start])

        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if v not in color:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return False

    return True


def is_bipartite_dfs(graph):
    color = {}

    def dfs(u, current_color):
        color[u] = current_color
        for v in graph[u]:
            if v not in color:
                if not dfs(v, 1 - current_color):
                    return False
            elif color[v] == color[u]:
                return False
        return True

    for start in graph:
        if start not in color and not dfs(start, 0):
            return False

    return True


bipartite_graph = {
    0: [1, 3],
    1: [0, 2],
    2: [1, 3],
    3: [0, 2],
    4: [5],
    5: [4],
}

odd_cycle_graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1],
}

print('BFS bipartite:', is_bipartite_bfs(bipartite_graph))
print('DFS bipartite:', is_bipartite_dfs(bipartite_graph))
print('BFS odd cycle:', is_bipartite_bfs(odd_cycle_graph))
print('DFS odd cycle:', is_bipartite_dfs(odd_cycle_graph))

预期输出

text
BFS bipartite: True
DFS bipartite: True
BFS odd cycle: False
DFS odd cycle: False

BFS 和 DFS 都只会把每个顶点染色一次,并检查每条边有限次。使用邻接表时,时间复杂度都是 O(V+E)O(V+E),颜色表以及 BFS 队列或 DFS 调用栈需要 O(V)O(V) 级额外空间。

容易漏掉的边界情况

自环是最直接的冲突。如果顶点存在一条指向自身的边,那么这条边要求同一个顶点同时具有两种不同颜色,因此图一定不是二分图。上面的实现会在检查该邻居时发现颜色相同并返回 False。

输入邻接表还应与问题的图模型一致。对于无向图,一条边通常应在两个端点的邻接表中都出现;如果只记录单向关系,搜索可能遗漏本应检查的约束。若原问题是有向图,则应先明确所谓“二分”是按方向定义,还是忽略方向后判断其底层无向图。

实际选择 BFS 还是 DFS 通常不会改变复杂度。需要按层观察染色过程、避免深递归时更适合 BFS;已有 DFS 框架或还要同时完成连通分量遍历时,DFS 往往更顺手。真正决定正确性的不是搜索顺序,而是每条边都必须满足两端颜色相反这一约束。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二分图怎样用染色判断

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通