求基于BFS查找图的双连通分量（块）的代码

双连通分量的BFS实现核心是跟踪每个节点的遍历深度、能通过回边到达的最浅深度，同时用栈保存遍历过程中的边，当判定某个节点为割点时，从栈中提取对应的双连通分量。以下是Python实现代码：

from collections import deque

def bfs_biconnected_components(graph):
    n = len(graph)
    # 记录节点的遍历深度，未访问为-1
    depth = [-1] * n
    # 记录节点能通过回边到达的最小深度
    low = [-1] * n
    # 记录父节点
    parent = [-1] * n
    # 保存遍历过程中的边，用于提取分量
    edge_stack = []
    # 存储所有双连通分量（每个分量是边的集合）
    components = []

    # 遍历所有节点，处理非连通图
    for start in range(n):
        if depth[start] == -1:
            queue = deque()
            queue.append(start)
            depth[start] = 0
            low[start] = 0
            # 避免节点重复入队
            in_queue = set()
            in_queue.add(start)

            while queue:
                u = queue.popleft()
                in_queue.remove(u)

                for v in graph[u]:
                    if depth[v] == -1:
                        # 未访问节点，作为子节点处理
                        parent[v] = u
                        depth[v] = depth[u] + 1
                        low[v] = depth[v]
                        edge_stack.append((u, v))
                        queue.append(v)
                        in_queue.add(v)
                    elif parent[u] != v and depth[v] < depth[u]:
                        # 遇到回边（非父节点且v在u的上层）
                        edge_stack.append((u, v))
                        # 更新当前节点的low值
                        if low[u] > depth[v]:
                            low[u] = depth[v]
                            # 重新入队u，以便更新其子节点的low值
                            if u not in in_queue:
                                queue.append(u)
                                in_queue.add(u)

                # 检查当前节点的子节点，判定割点并提取分量
                for v in graph[u]:
                    if parent[v] == u and low[v] >= depth[u]:
                        # 子节点无法通过回边到达比u更早的节点，u是割点
                        component = []
                        # 弹出栈中直到当前边的所有边，组成分量
                        while True:
                            edge = edge_stack.pop()
                            component.append(edge)
                            if edge == (u, v) or edge == (v, u):
                                break
                        components.append(component)

            # 处理根节点剩余的边（根节点有多个子节点时，最后剩余边组成分量）
            if edge_stack:
                components.append(edge_stack.copy())
                edge_stack.clear()

    return components

# 示例测试
if __name__ == "__main__":
    # 邻接表表示的图
    graph = [
        [1, 2],
        [0, 2, 3],
        [0, 1, 4],
        [1, 4],
        [2, 3]
    ]

    bcc = bfs_biconnected_components(graph)
    print("双连通分量（边集合）：")
    for idx, comp in enumerate(bcc, 1):
        print(f"分量 {idx}: {comp}")

关键逻辑说明 #

• depth数组：标记每个节点的遍历层次，用于区分节点的访问状态和层级关系。
• low数组：核心变量，记录节点能通过回边到达的最浅深度，用于判定割点。
• 边栈：保存遍历中经过的边，当发现割点时，从栈中弹出对应边形成双连通分量。
• 回边处理：遇到已访问的非父节点且层级更高的节点时，更新当前节点的low值，并重新入队当前节点以更新其子节点的low值。
• 割点判定：当子节点的low值大于等于当前节点的深度时，说明当前节点是割点，此时提取对应双连通分量。

内容的提问来源于stack exchange，提问作者Mantas Donela