如何优化图组件查找效率？避免重复执行BFS遍历节点

原代码的components方法效率低下的核心问题是对每个节点都执行完整BFS，且重复处理已发现的连通组件，时间复杂度高达O(N*(N+E))。下面是优化后的实现，通过全局标记已访问节点，确保每个节点仅被遍历一次，时间复杂度降至最优的O(N+E)：

class Graph:     # 图数据结构类
    def __init__(self, num_nodes, edges):
        self.num_nodes = num_nodes
        self.data = [[] for _ in range(num_nodes)]
        for n1, n2 in edges:
            self.data[n1].append(n2)
            self.data[n2].append(n1)

    def bfs(self, root, visited):
        # 修改BFS方法，传入外部的visited数组避免重复创建
        queue = []
        distance = [None] * len(self.data)
        parent = [None] * len(self.data)

        visited[root] = True
        distance[root] = 0
        queue.append(root)
        idx = 0

        while idx < len(queue):
            current = queue[idx]
            idx += 1

            for node in self.data[current]:
                if not visited[node]:
                    visited[node] = True
                    distance[node] = 1 + distance[current]
                    parent[node] = current
                    queue.append(node)

        return set(queue), distance, parent

    def components(self):
        components = []
        visited = [False] * self.num_nodes  # 全局标记已访问节点
        for i in range(self.num_nodes):
            if not visited[i]:  # 仅对未访问节点启动BFS
                component, _, _ = self.bfs(i, visited)
                components.append(component)
        return components

关键优化点 #

• 全局共享visited数组：在components方法中初始化一次标记数组，所有BFS操作共用该数组，确保节点被访问后不会重复处理
• 按需触发BFS：只有遇到未访问的节点时，才启动BFS遍历其所在的完整连通组件，一次性标记组件内所有节点为已访问
• 复用BFS逻辑：修改原BFS方法接收外部的visited数组，减少重复创建数组的开销

如果更偏好简洁的实现，也可以用DFS替代BFS，效率一致：

class Graph:
    # 保留__init__方法不变
    def __init__(self, num_nodes, edges):
        self.num_nodes = num_nodes
        self.data = [[] for _ in range(num_nodes)]
        for n1, n2 in edges:
            self.data[n1].append(n2)
            self.data[n2].append(n1)

    def dfs(self, node, visited, component):
        visited[node] = True
        component.append(node)
        for neighbor in self.data[node]:
            if not visited[neighbor]:
                self.dfs(neighbor, visited, component)

    def components(self):
        components = []
        visited = [False] * self.num_nodes
        for i in range(self.num_nodes):
            if not visited[i]:
                component = []
                self.dfs(i, visited, component)
                components.append(set(component))
        return components

内容的提问来源于stack exchange，提问作者Touseef Ahmed