求最大连通分量代码python 案例分析

好的，下面是一个求图形最大连通分量的 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

# 创建一个新的 Graph 对象
g = Graph()

# 向图形中添加一些边
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(5, 6)
g.add_edge(6, 7)

# 求最大连通分量的大小
largest_size = g.largest_component()

# 输出结果
print("最大连通分量的大小为：", largest_size)

该代码首先定义了一个名为 Graph 的类，它包含了我们前面讨论的 add_edge、DFS 和 largest_component 方法。然后，我们创建一个 Graph 对象 g，并向其添加一些边。最后，我们调用 g.largest_component() 方法来计算最大连通分量的大小，并将其存储在 largest_size 变量中。最终，我们输出结果。

在该代码中，我们使用了 Python 内置模块 collections 中的 defaultdict 类来创建邻接列表。我们还使用了深度优先搜索算法来遍历图形，并使用 visited 数组来跟踪每个顶点是否被访问过。通过遍历图形中的每个顶点，并使用 DFS 方法遍历与该顶点相关的所有节点，我们可以计算最大连通分量的大小。