HashSetを使用したO（1）ルックアップ時間の隣接リスト

私のアルゴリズムクラスでは、グラフ表示の隣接リストの引き戻しは、各ノードに対応する隣接ノードの配列を反復するO（n）ルックアップ時間であると言われています。私は自分の隣接ノードのHashSetにマップするHashMapを使って自分の隣接リストを実装していますが、O（1）ルックアップしか取らないでしょうか？私は行方不明のものがありますか？HashSetを使用したO（1）ルックアップ時間の隣接リスト

出典

2017-03-26 discuit

あなたが知っているように、HashMapのキーを使って値を調べるのはO（1）です。ただし、隣接リストでは、HashMapの値も隣接するノードのリストです。隣接リストの主な目的は、隣接ノードを反復することです。たとえば、DFSやBFSのようなグラフトラバーサルアルゴリズム。あなたのケースでは、HashSet。 HashSetの要素の数をnとします。次に、HashSet内のすべての要素を反復するために、O（n）があります。

So, total complexity would be O(1)+O(n). 

    Where O(1)= look up in HashMap 
      O(n)= iterate all the elements

一般的に、疎なグラフの場合、隣接リストはほんの僅かなエッジしか持たないグラフなので好ましいです。これは、各ノード（HashMapのキー）内の隣接する要素の数が少ないことを意味します。要素を探すことはそれほどコストがかかりません。

出典

2017-03-26 03:43:21

私はHashSetの意味を明確にしていません。私は自分のキーの値としてHashSetデータ構造（基本的にO（1）ルックアップ時間の要素のセット）を使用していることを意味していました。私が正しいとすれば、私の価値は、私がHashSetという名前のジェネリックリストであると思ったのです。 – discuit

ええええええええええええええええええええええええええええええええええええリストの主な目的は隣接ノードを保存することです、そして、それらのノードがDFSのようなアルゴリズムに必要とされている時はいつでも使用し、すべてを繰り返します。ですから、HashSetを使用すると、複雑さもO（n）回繰り返されます。 HashSetはO（1）です。あなたは正しいです。私の更新された答えを見てください。今は明らかだと思います。 –

私は自分の隣接ノードのを設定し、ハッシュにノードをマップするHashMapを使用して、私の隣接リストを実装して、O（1）時間を見てかかるだろうではないことだけ？ [重点鉱山]

右—が、「adjacency list」は、通常、アレイまたはリンクされたリストではなく、HashSetのような表現を意味します：つまり、隣接リストは、むしろ頂点の隣人を反復処理するために最適化されています2つの頂点が隣接しているかどうかを照会するよりも

出典

2017-03-26 04:19:46 ruakh

HashSetを使用したO（1）ルックアップ時間の隣接リスト

答えて

関連する問題