使用循环查找图中所有连接的节点

Question

我已经在这个问题上坐了好几天了，但不幸的是，我在这里找不到对我有帮助的答案（而且我进行了很多搜索），而且我没有运气自己实施正确的解决方案。

所以，我有一个带有循环的图，我想从所有节点（不包括与其自身连接的节点）中找到所有连接的节点。例如

1 -> 3 -> 4  
2 -> 4  
3 -> 2    
4 -> 5, 3  
5 -> NULL

输出应该是：（顺序无关）

1 -> {2, 3, 4, 5}
2 -> {4, 3, 5}
3 -> {2, 4, 5}
4 -> {2, 3, 5}
5 -> NULL

我能找到的最接近的解决方案是 THIS 一个，但不幸的是，这对我的问题不起作用，因为我有循环（因此我总是得到无穷无尽的递归）而且我不知道如何更正那里给出的代码，以便循环也被接受。

如有任何帮助，我们将不胜感激！

Answer 1

您可以使用递归生成器函数来查找连接：

首先，创建图表：

s = """
1 -> 3 -> 4
2 -> 4
3 -> 2
4 -> 5, 3
5 -> NULL
"""
from itertools import product as pr
def to_graph():
   for i in filter(None, s.split('\n')):
      d = [tuple(int(l) if l.isdigit() else None for l in k.split(', ')) for k in i.split(' -> ')]
      for j in range(len(d)-1):
         yield from pr(d[j], d[j+1])

graph = list(to_graph())
#[(1, 3), (3, 4), (2, 4), (3, 2), (4, 5), (4, 3), (5, None)]

然后，寻找联系：

from collections import defaultdict
def connections(d, n, c = [], s = []):
   if not (k:=[b for a, b in graph if a == n and b not in c]):
      yield (d, c+[n])
      if (l:=[a for a, _ in graph if a not in s+[d]]):
        yield from connections(l[0], l[0], c = [], s=s+[d])
   else:
      yield from [j for i in k for j in connections(d, i, c=c+[n], s = s)]
      
result = defaultdict(set)
for a, b in connections(graph[0][0], graph[0][0]): #choosing `1` as the starting node, but any other node in `graph` will work as well
   for i in filter(lambda x:x != a, b):
      result[a].add(i)

#formatting results to match your desired output
print({a:k if (k:=set(filter(None, b))) else None for a, b in result.items()})

输出：

{1: {2, 3, 4, 5}, 3: {2, 4, 5}, 2: {3, 4, 5}, 4: {2, 3, 5}, 5: None}

为了防止递归深度错误，connections 保留一个运行之前在路径遍历期间收集的所有节点的列表，并在递归发生之前根据该列表检查路径的潜在添加再次.

Answer 2

我们可以保留一份运行所有联系和保释的清单，只要它们不变。

graph = {
    1: {3},
    2: {4},
    3: {2, 4},
    4: {5, 3},
    5: set(),
}

connectedness = {**graph}
while True:
    new_connectedness = {v: n.union(*[connectedness[nn] for nn in n]) 
                         for v, n in connectedness.items()}
    if new_connectedness == connectedness:
        break
    connectedness = new_connectedness
    
connectedness = {v: c - {v} for v, c in connectedness.items()}

每次通过循环，节点连接到的边集都会更新为已连接到的所有节点。一旦没有任何变化，我们就会保释。然后我们通过删除自连接来规范化。

Answer 3

您正在尝试计算带环的有向图的传递闭包。您可以在 O(V²) 时间内执行此操作，如下所示：

例如，使用 Tarjan's algorithm 查找图中的强连通分量。
将每个 SCC 折叠成一个顶点。请记住，它们都具有相同的可达顶点集，并且它们都可以相互到达。折叠 SCC 后，结果是 DAG。
以相反的拓扑顺序处理顶点以找到每个 SCC 的可达性集，如 this answer for DAGs that you already found。

使用循环查找图中所有连接的节点

Find all connected nodes in graph with loops

python

algorithm

graph

python-3.x