python - 从边列表计算创建的图数和每个图中的顶点数

Question

给定边列表，例如 edges = [[1,2],[2,3],[3,1],[4,5]]

我需要找出创建了多少图，我的意思是这些边创建了多少组组件。然后获取组件组中的顶点数。

但是，我需要能够处理 10^5 条边，而我目前无法完成大量边的任务。

我的算法目前正在获取 edges= [[1,2],[2,3],[3,1],[4,5]] 的列表，如果它们有交集，则将每个列表合并为集合，这将输出一个新列表，该列表现在包含组组件，例如 , graphs = [[1,2,3],[4,5]]

有两个连通分量:[1,2,3] 连通，[4,5] 也连通。

我想知道是否有更好的方法来完成这项任务。

def mergeList(edges):
    sets = [set(x) for x in edges if x]
    m = 1
    while m:
        m = 0
        res = []
        while sets:
            common, r = sets[0], sets[1:]
            sets = []
            for x in r:
                if x.isdisjoint(common):
                    sets.append(x)
                else:
                    m = 1
                    common |= x
            res.append(common)
        sets = res
    return sets

我想尝试在字典或其他有效的东西中这样做，因为这太慢了。

Answer 1

Python 中的基本迭代图遍历还不错。

import collections


def connected_components(edges):
    # build the graph
    neighbors = collections.defaultdict(set)
    for u, v in edges:
        neighbors[u].add(v)
        neighbors[v].add(u)
    # traverse the graph
    sizes = []
    visited = set()
    for u in neighbors.keys():
        if u in visited:
            continue
        # visit the component that includes u
        size = 0
        agenda = {u}
        while agenda:
            v = agenda.pop()
            visited.add(v)
            size += 1
            agenda.update(neighbors[v] - visited)
        sizes.append(size)
    return sizes