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

Question

Python数据结构，利用广度优先搜索编程实现确定无向图的连通分量。

Answer 1

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]