Python網絡x：獲取每個節點的所有可能的目的地

Question

我的圖形措辭可能是關閉的，道歉。
給定一個有向圖，我想獲得一個字典，其中的關鍵字是一個節點，並且該值是我們可以使用任何路徑從此節點到達的所有節點的集合。
如在該圖中：

1->2->3 
4->5 

我們應該得到這樣的結果：

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

我能得到通過調用是這樣的：

{n: networkx.bfs_tree(graph, n).nodes() for n in networkx.nodes(graph)} 

但它意味着爲O（n^2）迭代，而這可以用O（n）迭代來構建。

我錯過了什麼？

謝謝！

Answer 1

優化：我們可以從底層節點的連接樹中重建BFS。因此，遞歸解決方案（非循環只圖）：

d = {} 
def foo(node): 
    if node in d: 
     return d[node] 
    nodes = g.neighbors(node) 
    d[node] = set(nodes) 
    for neighbor in nodes: 
     d[node].update(foo(neighbor)) 
    return d[node].union(nodes) 

測試：

> _=[foo(node) for node in g.nodes()] 
> d 
{1: set([2, 3]), 2: set([3]), 3: set([]), 4: set([5]), 5: set([])} 

假設緩存的電話是免費的，它應該是O（E）