最大连通分量代码
时间: 2023-06-22 09:22:18 浏览: 65
以下是使用深度优先搜索(DFS)算法求解无向图最大连通分量的代码示例:
```python
# 无向图最大连通分量
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def DFS(self, v, visited):
visited[v] = True
for i in self.graph[v]:
if not visited[i]:
self.DFS(i, visited)
def largest_component(self):
visited = [False] * (max(self.graph) + 1)
max_component_size = 0
for i in self.graph:
if not visited[i]:
component_size = 0
self.DFS(i, visited)
for j in visited:
if j:
component_size += 1
max_component_size = max(max_component_size, component_size)
return max_component_size
```
在这个代码示例中,我们使用了一个字典来表示无向图。通过 `add_edge()` 方法添加边。然后我们使用深度优先搜索算法来遍历图中所有的连通分量,并计算其中最大连通分量的大小。
在 `largest_component()` 方法中,我们首先创建一个布尔类型的列表 `visited` 来记录每个节点是否被访问过。然后,我们遍历整个图,对于每个未被访问的节点,我们进行深度优先搜索,并将访问到的节点标记为已访问。在搜索结束后,我们遍历 `visited` 列表,计算连通分量的大小。最后,我们将最大连通分量的大小返回。
注意,这里假设节点的编号从 0 开始,如果不是,需要对 `visited` 列表初始化时的大小进行修改。