Python networkx：すべてのノードの可能なすべての宛先を取得します。

Question

私のグラフの文言は、謝罪するかもしれません。
与えられた有向グラフでは、キーがノードである辞書を取得したいと思います。その値は、任意のパスを使用してこのノードから到達できるすべてのノードのセットです。このグラフ上の
例：N（

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

しかし、それはOを意味します

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

が、私はこのような何かを呼び出すことであることを得ることができる：私たちはこの結果を取得する必要があります

1->2->3 
4->5 

^2）iterations、これは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）