利用广度优先搜索编程实现确定无向图的连通分量。python

以下是利用广度优先搜索实现无向图连通分量的 Python 代码：

from collections import deque

def bfs(graph, visited, node):
    """从 node 开始进行 BFS，返回与 node 连通的所有节点"""
    connected = []
    queue = deque()
    queue.append(node)
    visited[node] = True
    while queue:
        curr_node = queue.popleft()
        connected.append(curr_node)
        for neighbor in graph[curr_node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
    return connected

def connected_components(graph):
    """返回无向图 graph 的所有连通分量"""
    visited = {node: False for node in graph}
    components = []
    for node in graph:
        if not visited[node]:
            connected = bfs(graph, visited, node)
            components.append(connected)
    return components

其中，`bfs` 函数实现了从一个节点开始进行 BFS，返回与该节点连通的所有节点。`connected_components` 函数实现了返回无向图的所有连通分量。这里使用了一个字典 `visited` 记录所有节点的访问状态，初始化为 False。然后对于每个节点，如果它没有被访问过，则进行 BFS，并将返回的连通节点列表加入到结果列表中。最后返回所有连通分量的列表。

使用示例：

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

components = connected_components(graph)
print(components) # 输出 [[1, 2, 3, 4, 5]]

这里我们定义了一个简单的无向图，包含了 5 个节点和 5 条边。运行 `connected_components` 函数，可以得到该无向图的连通分量，即包含所有节点的一个列表。