计算图中的所有连接节点

Question

我有一个> 10k的（无序）数字对列表。我想将它们直接或间接地分类为连接对的集合。我认为这对应于无向图。我使用python，并试图像这样来表示这种结构。

为了知道所有连接到数字i，我可以检查是否有从路径i到j所有j在列表除外i。但是，使用此实现，对于我正在处理的列表大小而言，计算时间变得太长。有没有更有效的方法可以做到这一点？（或者是否已经建立了python库？）

Answer 1

It sounds as though you are interested in computing the connected components of a graph. I would suggest looking into the networkx package and its tools for computing components.

For example, suppose our data is a list of pairs of numbers, each pair representing an edge in the graph:

pairs = [
    (1, 2),
    (2, 4),
    (3, 5),
    (2, 5),
    (7, 9),
    (9, 10),
    (8, 7)
]

In the graph represented by these edges, there is a path between any pair of nodes in the set {1, 2, 3, 4, 5}, and there is also a path between any pair of nodes in {6, 7, 8, 9, 10}. But there is no path, say, from 5 to 7. This is to say that there are two connected components in the graph.

To discover these components, we first import networkx and create a graph:

>>> import networkx as nx
>>> graph = nx.from_edgelist(pairs)

计算组件非常简单

>>> list(nx.connected_components(graph))
>>> [{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}]

nx.connected_components 是一个生成器，因此在这里我们将结果转换为一个列表，以显示所有连接的组件。

我们还可以找到包含给定节点的连接组件：

>>> nx.node_connected_component(graph, 3)
{1, 2, 3, 4, 5}

我们还可以快速计算已连接组件的数量：

>>> nx.number_connected_components(graph)
2