13

面接の準備とグラフの実装のレビューを行っています。私が見続けている大きなものは、隣接リストと隣接行列です。基本的な操作の実行時間を考えると、ハッシュが使用されているデータ構造が見られないのはなぜですか?

たとえば、Java では、隣接リストは一般的ArrayList<LinkedList<Node>>に ですが、なぜ人々は を使用しないのHashMap<Node, HashSet<Node>>でしょうか?

n = ノード数、m = エッジ数とします。

どちらの実装でも、ノード v を削除するには、すべてのコレクションを検索して v を削除する必要があります。隣接リストでは O(n^2) ですが、「隣接セット」では O(n) です。同様に、エッジを削除するには、v のリストからノード u を削除し、u のリストからノード v を削除する必要があります。隣接リストでは O(n) ですが、隣接セットでは O(1) です。ノードの後継ノードの検索、2 つのノード間にパスが存在するかどうかの検索などの他の操作は、両方の実装で同じです。空間複雑度も両方とも O(n + m) です。

私が考えることができる隣接セットの唯一の欠点は、ノード/エッジの追加が O(1) に償却されることですが、隣接リストでそうすることは本当に O(1) です。

おそらく、私は何かを見ていないか、ランタイムを計算するときに物事を考慮するのを忘れていたので、私に知らせてください.

4

4 に答える 4

8

DavidEisenstatの答えと同じ考え方で、グラフの実装は大きく異なります。これは、講義ではうまくいかないことの 1 つです。2 つの概念設計があります。

1) Adjacency list
2) Adjacency matrix

ただし、挿入/削除/検索の高速化などのプロパティを取得するために、どちらの設計も簡単に拡張できます。多くの場合、価格は余分なデータを保存するだけです! 比較的単純なグラフ アルゴリズム (オイラーなど) の実装を検討し、グラフの実装がランタイムの複雑さにどのように大きな影響を与えるかを確認してください。

私の言いたいことをもう少し明確にするために、「隣接リスト」ではLinkedList. たとえば、ウィキは自分のページでこれを引用しています：

Guido van Rossum によって提案された実装では、ハッシュ テーブルを使用して、グラフ内の各頂点を隣接する頂点の配列に関連付けます。この表現では、頂点は任意のハッシュ可能なオブジェクトで表すことができます。オブジェクトとしてのエッジの明示的な表現はありません。

于 2013-08-20T02:23:57.527 に答える
2

グラフ内に任意のエッジがあるかどうかを確認する必要はめったになく (これに依存する日常的なグラフ アルゴリズムは考えられません)、必要な場合は 1 つだけを使用できるため、通常はこの表現を目にすることはありません。(v1, v2)エッジを表すペアを格納する、グラフ全体のハッシュ マップ。これはより効率的なようです。

(一般的なグラフ アルゴリズムのほとんどは、「頂点 v のすべての隣人に対して、... を行う」などのことを言い、隣接リストは完璧です。)

于 2016-11-25T10:33:13.457 に答える