この単純なグラフで、あるノードの到来するアーク/エッジをすべて見つける方法を教えてください。

Question

グラフの実装方法はhttps://www.python.org/doc/essays/graphs/です。問題は、あるノードへのすべての着信アークをできるだけ速く見つける方法を混乱させることです。

graph = {'A': ['B', 'C'], 
      'B': ['C', 'D'], 
      'C': ['D'], 
      'D': ['C'], 
      'E': ['F'], 
      'F': ['C']} 

ノードCには、ノードA、B、D、Fからのアークがあることがわかります。問題は、どのようにしてノードA、B、D、Fをキーの辞書の各リストに入れずにチェックして、Cが含まれているかを調べる方法です。これを行う方法や効率的なグラフとメソッドがありますか？誰かが正しい方向に私を向けることができます、事前に感謝します。

Answer 1

あなたは、あなたが同じようtargetにノードのインシデントを確認することができ、単にset構造

graph = {'A': {'B', 'C'}, # If you're using python 2.7+ you can initalize a set like this 
     'B': {'C', 'D'}, 
     'C': {'D'}, 
     'D': {'C'}, 
     'E': set(['F']), # Set initialization pre-2.7 
     'F': set()}  # Empty set initialization, can't use {} 

を使用して隣接行列に似た何かを得ることができます。

[pointsFrom for (pointsFrom, pointsTo) in graph.items() if target in pointsTo] 

これは、実行中の時間を持つことになりますあなたのグラフのノード数で線形です。