Python数据结构，利用广度优先搜索编程实现确定无向图的连通分量。
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = [[] for _ in range(num_vertices)]
def add_edge(self, u, v):
self.adj_list[u].append(v)
self.adj_list[v].append(u)
def bfs(graph, start, component_num, component):
queue = [start]
component[start] = component_num
while queue:
vertex = queue.pop(0)
for neighbor in graph.adj_list[vertex]:
if component[neighbor] is None:
queue.append(neighbor)
component[neighbor] = component_num
def get_connected_components(graph):
component_num = 0
component = [None] * graph.num_vertices
for vertex in range(graph.num_vertices):
if component[vertex] is None:
bfs(graph, vertex, component_num, component)
component_num += 1
return component
# 创建图
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
# 获取连通分量
components = get_connected_components(g)
print(components) # 输出：[0, 0, 0, 1, 2]
下面是详细代码实现和注释，望采纳
from collections import deque
def get_connected_components(graph):
# 初始化所有节点的访问状态为未访问
visited = {node: False for node in graph}
# 初始化连通分量列表
connected_components = []
# 对每一个未访问过的节点执行广度优先搜索
for node in graph:
if not visited[node]:
# 执行广度优先搜索
component = bfs(graph, node, visited)
# 将搜索结果加入连通分量列表
connected_components.append(component)
return connected_components
def bfs(graph, start_node, visited):
# 初始化队列和连通分量
queue = deque()
component = []
# 将起始节点加入队列并标记为已访问
queue.append(start_node)
visited[start_node] = True
# 当队列不为空时，继续搜索
while queue:
# 从队列中取出下一个节点
node = queue.popleft()
# 将节点加入连通分量
component.append(node)
# 搜索与当前节点相连的所有未访问过的节点
for neighbor in graph[node]:
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
return component