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]

这段代码实现了无向图的连通分量计算。首先，使用 Graph 类定义了一个图对象，包含节点数和邻接表。然后，使用 add_edge 方法向图中添加边。

接下来，使用 BFS 算法遍历图中的所有节点，并将每个节点所属的连通分量编号存储在 component 数组中。具体实现如下：

1. 遍历图中的所有节点，如果该节点的连通分量编号为 None，则使用 BFS 算法计算该节点所属的连通分量编号。

2. 在 BFS 算法中，使用队列 queue 存储待遍历的节点，将起始节点 start 加入队列中。

3. 当队列不为空时，从队列中取出一个节点 vertex，遍历其所有相邻节点 neighbor。

4. 如果相邻节点 neighbor 的连通分量编号为 None，则将其加入队列中，并将其连通分量编号标记为当前的连通分量编号 component_num。

5. 重复步骤 3 和 4，直到队列为空为止。

6. 返回标记好连通分量编号的数组 component。

最后，将所有节点所属的连通分量编号组成的数组 component 返回。该算法的时间复杂度为 O(V+E)，其中 V 表示节点数，E 表示边数，与图的规模相关。对于给定的无向图，该算法可以准确地计算出所有的连通分量。在代码示例中，输出的结果为 [0, 0, 0, 1, 2]，表示图中包含 3 个连通分量，分别为 0 号连通分量（包含节点 0、1、2）、1 号连通分量（包含节点 3）和 2 号连通分量（包含节点 4）。

相关问题

解释这段代码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)

这段代码定义了一个名为Graph的类，它表示一个无向图。构造函数__init__接收参数num_vertices，表示图中节点的数量，然后初始化一个大小为num_vertices的空邻接表adj_list。邻接表是一个列表，其中包含了每个节点的邻居节点。每个邻居列表初始化为空列表[]。

add_edge方法用于向图中添加一条边。它接受两个参数u和v，表示两个节点之间存在一条边。它将v添加到u的邻居列表中，并将u添加到v的邻居列表中，因为这是一个无向图，边是双向的。

例如，如果我们要创建一个包含4个节点的无向图，可以这样做：

g = Graph(4)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 0)

这将创建一个环形图，其中每个节点都与相邻的两个节点相连。

按照如下定义给G=Graph()添加边举例子class Graph: def __init__(self): self.vertices = {} self.numVertices = 0 # 初始图 顶点0 def addVertex(self, key): # add顶点 self.numVertices = self.numVertices + 1 newVertex = Vertex(key) self.vertices[key] = newVertex # 顶点对应属性 return newVertex def getVertex(self, key): if key in self.vertices: return self.vertices[key] else: return None def __contains__(self, key): # check判断是否存在 return key in self.vertices def addEdge(self, f, t, cost): # 添加边 if f not in self.vertices: nv = self.addVertex(f) # 顶点未在图的顶点集先加入 if t not in self.vertices: nv = self.addVertex(t) self.vertices[f].addNeighbor(self.vertices[t], cost) # 添加邻接点

好的，假设我们要给这个图添加一条从顶点0到顶点1的边，边权为2，代码如下：

G = Graph()
G.addVertex(0)
G.addVertex(1)
G.addEdge(0, 1, 2)

这样就在图中添加了一条从顶点0到顶点1的边，边权为2。