python - 查找图中所有有循环的连接节点

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

我们可以保留所有关联性的运行列表，并在它们没有改变时立即取消。

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()}

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