パイソン - グラフを実装し、エッジと頂点

Question

どのように、どのようなグラフの次の実装ごとにhasConnection()機能を実装するための最も効率的な方法だろうとの間の接続を確認します。これは、2つの頂点の間に接続があるかどうかをチェックできる関数を意味します。 hasConnection(vertex1, vertex2)

実装A：未分類の隣接リストの辞書で表されます。例えば。ソートされた隣接の辞書を含む辞書で表さ：グラフは、頂点A、B、CおよびD Aは、BとDに接続されていた場合、これは

{A:[D, B], B:[A], C:[], D:[A]}

実装Bとして示されるであろうリスト。内側の辞書には 'adjacentVertices'という名前のキーがあります。例えば。鍵有する辞書を含む辞書で表さ：グラフは、頂点A、B、CおよびD Aは、BとDに接続されていた場合、これは

{A:{adjacentVertices:[B, D]}, B:{adjacentVertices:[A]}, C:{adjacentVertices:[]}, D:{adjacentVertices:[A]}}

実施Cとして示されるであろう値 'ヌル'。キーは、隣接する頂点を表します。例えば。グラフは、頂点A、B、CおよびD Aは、これが最終的に

{A:{B:null, D:null}, B:{A:null}, C:{}, D:{A:null}}

として示されるであろうBおよびDへの接続を有している場合、コードが実装ごとになるように何を必要としますhasConnection()の最も効率的なバージョンはどれですか？

Answer 1

NがV1で始まるエッジの数である。まず、ソートされていない隣接リストは、含まれているチェック（反復）がO(N)ある：

graph = {A:[D, B], B:[A], C:[], D:[A]} 
def has_connection(graph, v1, v2): 
    return v2 in graph.get(v1, []) 

第二に、ソートされた隣接リストため、チェックが含まれてい

graph = {A: {'adjacentVertices': [B, D]}, B: {'adjacentVertices': [A]}, C: {'adjacentVertices': []}, D: {'adjacentVertices': [A]}} 
import bisect 
def has_connection(graph, v1, v2): 
    vs = graph.get(v1, {}).get('adjacentVertices', []) 
    try: 
     return v2 == vs[bisect.bisect_left(vs, v2)] 
    except IndexError: 
     return False 

最後に、隣接辞書のために、含まチェック（ハッシュルックアップ）がO(1)ある：NがV1で始まるエッジの数である（bisectを使用してバイナリサーチ）がO(log N)でありますしたがって、第3の実施形態は第2の実施形態より速く、第2の実施形態は第1の実施形態より速く、第2の実施形態は第1の実施形態よりも速い。これは、それぞれのアルゴリズムの固有の利点が実装上のオーバーヘッドを上回る十分に大きなグラフに対してのみ有効です。 「hasConnection」唯一の最も効率的な方法について