如何让组件功能更高效？

Question

我对图数据结构的实现，以查找图中的组件数量

class Graph:     # This is class of the graph data structure
def __init__(self, num_nodes, edges):
    self.num_nodes = num_nodes
    self.data = [[] for i in range(num_nodes)]
    for n1, n2 in edges:
        self.data[n1].append(n2)
        self.data[n2].append(n1)

def bfs(self, root):      # using breadth first search algorithm
    queue = []
    discovered = [False] * len(self.data)
    distance = [None] * len(self.data)
    parent = [None] * len(self.data)

    discovered[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 discovered[node]:
                discovered[node] = True
                distance[node] = 1 + distance[current]
                parent[node] = current
                queue.append(node)

    return set(queue), distance, parent

def components(self): # listing the components of the graph
    components = []
    for i in range (0, len(self.data)):
        component = self.bfs(i)[0]
        if component not in components:
            components.append(component)
    return components

我想跳过在每个节点上重复执行 bfs 以找到图上的连接组件。

Answer 1

我想跳过在每个节点上重复执行 bfs 以找到图上的连接组件。

这当然是没有必要的。您只需为图中的每个组件运行一次 BFS。

- SET CN = 0
- MARK every vertex unvisited
- LOOP V over vertices
       - IF V unvisited
           - DO BFS from V, marking vertices as they are visited
           - INCREMENT CN