当前位置：首页 > article >正文

python 实现BFS判断是否是二分图Bipartite算法

article 2024/10/11 20:51:52

BFS判断是否是二分图Bipartite算法介绍

在图论中，二分图（Bipartite Graph）是一种特殊的图，其顶点可以被分成两个不相交的集合，使得图中的每一条边都连接着两个属于不同集合的顶点。检测一个图是否是二分图的一个常用算法是通过广度优先搜索（BFS）实现的。下面我将详细介绍如何使用BFS来判断一个图是否是二分图。

算法步骤

1、初始化：

给定一个无向图 G(V, E)，其中 V 是顶点集合，E 是边集合。
创建一个数组 color[] 来存储每个顶点的颜色（通常使用两个颜色，如0和1，或者更常用的是true和false）。未访问的顶点颜色初始化为一个特殊值（如 -1），表示尚未分配颜色。
创建一个队列 queue，用于BFS遍历。

2、选择起始点：

从图中的任意一个未访问的顶点 u 开始。
将 u 加入队列，并设置 color[u] = 0（或 true）。

3、BFS遍历：

当队列不为空时，执行以下步骤：
从队列中取出一个顶点 v。
遍历 v 的所有未访问的邻接点 w：
如果 w 未被访问（即 color[w] == -1）：
将 w 加入队列，并设置 color[w] = 1 - color[v]（即如果 v 是0，则 w 是1；反之亦然）。
如果 w 已被访问且 color[w] == color[v]：
这意味着存在一条连接相同颜色顶点的边，因此图不是二分图。返回 false。

4、完成遍历：

如果遍历结束且没有发现连接相同颜色顶点的边，则图是二分图。返回 true。

示例代码（Python）

from collections import deque

def isBipartite(graph):
    # 假设图用邻接表表示
    n = len(graph)
    color = [-1] * n  # 初始化为-1
    queue = deque()

    # 从任意顶点开始
    for i in range(n):
        if color[i] == -1:
            color[i] = 0
            queue.append(i)
            
            while queue:
                v = queue.popleft()
                for w in graph[v]:
                    if color[w] == -1:
                        color[w] = 1 - color[v]
                        queue.append(w)
                    elif color[w] == color[v]:
                        return False

    return True

# 示例
graph = [
    [1, 3],
    [0, 2],
    [1, 3],
    [2]
]
print(isBipartite(graph))  # 应该输出 True

注意：这个算法假设图是连通的。如果图不是连通的，你需要从每个未访问的顶点开始执行上述算法，并确保所有顶点都被检查。如果所有子图都是二分图，则整个图也是二分图。

BFS判断是否是二分图Bipartite算法python实现样例

下面是使用Python实现BFS判断是否是二分图的算法：

from collections import deque

def is_bipartite(graph):
    # 创建一个字典来存储每个节点的颜色，初始值为0
    color = {}
    for node in graph:
        color[node] = 0
    
    # 使用BFS遍历图中的每个节点
    for node in graph:
        if color[node] == 0:  # 当前节点还没有被染色
            queue = deque()
            queue.append(node)
            color[node] = 1  # 将当前节点染成颜色1
            
            while queue:
                current_node = queue.popleft()
                for neighbor in graph[current_node]:
                    if color[neighbor] == 0:
                        queue.append(neighbor)
                        # 将邻居节点染成与当前节点不同的颜色
                        color[neighbor] = 2 if color[current_node] == 1 else 1
                    elif color[neighbor] == color[current_node]:
                        return False  # 邻居节点与当前节点颜色相同，不是二分图
    
    return True  # 所有节点都遍历完，是二分图

# 示例
graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3]
}
print(is_bipartite(graph))  # 输出 True

graph = {
    1: [2, 3],
    2: [1, 3],
    3: [1, 2]
}
print(is_bipartite(graph))  # 输出 False