data-structures - 疎グラフと密グラフの違いは何ですか?

Question

疎なグラフを隣接リストで表し、密なグラフを隣接行列で表すのが理想的だと読みました。しかし、疎グラフと密グラフの主な違いを理解したいと思います。

Answer 1

密なグラフは、エッジの数が最大エッジ数に近いグラフです。 スパース グラフは、エッジの数が最小エッジ数に近いグラフです。スパース グラフは非接続グラフにすることができます。

Answer 2

名前が示すように、スパース グラフはまばらに接続されています (例: ツリー)。通常、エッジの数は O(n) です。ここで、n は頂点の数です。したがって、隣接リストはすべてのエッジに一定のスペースを必要とするため、優先されます。

密なグラフは密に接続されています。ここで、エッジの数は通常 O(n^2) です。したがって、隣接行列が優先されます。

比較のために、グラフに 1000 個の頂点があると仮定します。

グラフが密か疎かに関係なく、隣接行列には 1000^2 = 1,000,000 個の値を格納する必要があります。

グラフが最小限に接続されている (つまり、ツリーである) 場合、隣接リストには 2,997 個の値を格納する必要があります。グラフが完全に接続されている場合、3,000,000 の値を保存する必要があります。

Answer 3

C++ のオブジェクト指向設計パターンを使用したデータ構造とアルゴリズムから、p. 534、ブルーノ・P・ライス著：

非形式的に言えば、エッジが比較的少ないグラフは疎であり、エッジが多いグラフは密です。

定義 (スパース グラフ): スパース グラフはグラフ G = (V, E) で、|E| = O(|V|)。

定義（密グラフ） 密グラフとはグラフ G = (V, E) において |E| = Θ(|V| ² )。

Answer 4

主なグラフの積分特性は、頂点の数 V とエッジの数 E です。これら 2 つの関係によって、グラフが疎か密かが決まります (wiki ページはこちら)。

グラフのメモリ内表現を選択する背後にある理論全体は、サブジェクト ドメインと使用の詳細を考慮して、最適なアクセス時間とメモリ フットプリントのトレードオフを決定することです。

一般に、メモリ フットプリントを許容できない場合を除き、アクセス時間を O(1) にする (したがって、グラフを密な隣接行列として保存する) 必要があります。その場合は、最も適切な疎行列表現を選択します (wiki ページはこちら)。