计算图中的所有连接节点 [英] Counting all connected nodes in graph

问题描述

我有一个> 10k的(无序)数字对列表.我想将它们直接或间接地分类为连接对的集合.我认为这对应于无向图.我使用的是python，并尝试过类似此的方法来表示此结构.

I have a >10k list of (unordered) pairs of numbers. I'd like to classify them into sets of connected pairs either directly or indirectly. I think this corresponds to undirected graph. I'm using python, and tried something like this to represent this structure.

为了知道连接到 i 的所有号码，我可以检查列表中除 i 之外的所有 j ，是否存在从 i 到 j 的路径.但是，使用此实现，对于我正在处理的列表大小，计算时间变得太长.有没有更有效的方法可以做到这一点?(或者是否已经建立了python库?)

In order to know all the numbers connected to i, I can examine whether there is a path from i to j for all j in the list except i. However, with this implementation, the computation time gets too long for the size of list I'm dealing with. Is there a more efficient way to do this? (Or is there an already established python libraries?)

推荐答案

听起来好像您对计算图形的连接组件感兴趣.我建议研究 networkx 软件包及其

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)
]

在这些边所代表的图中，集合 {1、2、3、4、5} 中的任意一对节点之间都有一条路径，而在任何一对节点之间也有一条路径 {6，7，8，9，10} 中的一对节点.但是，例如，从 5 到 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.

要发现这些组件，我们首先导入 networkx 并创建一个图形:

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.connected_components is a generator, and so here we converted the result into a list in order to show all of the connected components.

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

We can also find the connected component containing a given node:

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

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

We can also quickly count the number of connected components:

>>> nx.number_connected_components(graph)
2

这篇关于计算图中的所有连接节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！