有没有一种简单的方法可以使用 python 找到所有连接的节点？

Question

A = ['node1', 'node2', 'node3', 'node4', 'node5'] #nodes
B = {'node1':'node2', 'node3':'node4', 'node4':'node5'} #connections

C = [['node1', 'node2'], ['node3', 'node4', 'node5']] #wanted result

我希望所有节点都相互连接；当输入是 A,B 时，我想要 C。

def demo(A, B): 
    # code
    return C

我尝试了一些复杂的方法来获得想要的结果，但没有成功。我希望有人能帮助我。

Answer 1

试试这个代码

只是循环字典，将键值对转换成列表

并将它们合并到一个单独的循环中

代码：

B1 = {'node1':'node2', 'node3':'node4', 'node4':'node5'}
B2 = {'node1':'node2', 'node3':'node4', 'node4':'node5', 'node5':'node6'}

def nodes_to_list(_dict):
  res = sorted([[i, j] for i, j in _dict.items()])

  for index1, i in enumerate(res):
    for index2, j in enumerate(res):
      if index1 != index2:
        if any(a in j for a in i):
          res[index1] = sorted(set(i+j))
          del res[index2]
  return res

print(nodes_to_list(B1))
print(nodes_to_list(B2))

输出：

[['node1', 'node2'], ['node3', 'node4', 'node5']]
[['node1', 'node2'], ['node3', 'node4', 'node5', 'node6']]

如果它不起作用请告诉我...

Answer 2

您可以使用递归生成器函数：

nodes = {'node1':'node2', 'node3':'node4', 'node4':'node5'}
def paths(n=None, c = []):
   if n is None:
      for a in nodes:
         if all(j != a for j in nodes.values()):
            yield from paths(a)
   elif n not in nodes:
      yield c+[n]
   else:
      yield from paths(nodes[n], c+[n])

print(list(paths()))

输出：

[['node1', 'node2'], ['node3', 'node4', 'node5']]

在更大的节点字典上：

nodes = {'node1':'node2', 'node3':'node4', 'node4':'node5', 'node5':'node6' }

输出：

[['node1', 'node2'], ['node3', 'node4', 'node5', 'node6']]

Answer 3

networkx 是一个选项：

import networkx as nx

# Initialize graph
G = nx.Graph()
# Put all your nodes into graph
G.add_nodes_from(A)
# Add edges to graph
for n1, n2 in B.items():
    G.add_edge(n1, n2)
# Create list of connected components of G
C = [list(c) for c in nx.connected_components(G)]

有没有一种简单的方法可以使用 python 找到所有连接的节点？

Is there a simple way to find all connected nodes using python?

python

algorithm

graph-theory