c++ - グラフ メモリの実装

Question

メモリ内のグラフを表現するために一般的に使用される 2 つの方法は、隣接リストまたは隣接行列を使用することです。隣接リストは、リンクされたリストへのポインターの配列を使用して実装されます。ベクトルのベクトルを使用するよりも高速である理由はありますか? バックトラッキングがはるかに簡単になるため、検索とトラバーサルが高速になるはずだと思います。

Answer 1

リンクされた隣接関係のベクトルは、実際には多くのバリエーションを持つお気に入りの教科書ミームです。確かに、ベクトルのベクトルを使用できます。違いは何ですか？

1 つは、リンク (とにかく 2 つのリンク) を使用すると、一定時間内にエッジを簡単に追加および削除できることです。これは明らかに、エッジ セットが縮小および拡大する場合にのみ重要です。エッジのベクトルを使用すると、個々の操作で O(k) が必要になる場合があります。ここで、k はインシデント エッジの数です。

注意: 隣接リストのエッジの順序がアプリケーションにとって重要でない場合は、ベクトルを使用して O(1) 個の削除を簡単に取得できます。最後の要素を削除する要素の位置にコピーしてから、最後の要素を削除するだけです! 残念ながら、隣接の順序が重要な場合 (たとえば、平面への埋め込みが心配な場合) はたくさんあります。

順序を維持する必要がある場合でも、コストをコピーして、多くの操作で操作ごとに平均 O(1) になるように調整できます。それでも一部のアプリケーションでは、これは十分ではなく、マークされた削除の数がベクトルの固定部分である場合にのみ圧縮が実行される「削除された」マーク (予約された頂点番号で十分) が必要です。コードは面倒で、すべての操作で削除されたノードをチェックすると、オーバーヘッドが追加されます。

もう 1 つの違いはオーバーヘッド スペースです。隣接リスト ノードは非常に小さく、ノード番号のみです。二重リンクには、数値自体の 4 倍のスペースが必要になる場合があります (数値が 32 ビットで、両方のポインターが 64 の場合)。非常に大きなグラフの場合、400% のスペース オーバーヘッドはあまり良くありません。

最後に、長期間にわたって頻繁に編集されるリンクされたデータ構造は、非常に不連続なメモリ アクセスにつながる可能性があります。これにより、ベクトルを介した線形アクセスと比較して、キャッシュのパフォーマンスが低下します。したがって、ここではベクトルが勝ちます。

ほとんどのアプリケーションでは、この違いは気にする必要はありません。繰り返しますが、巨大なグラフは現代世界のやり方です。

他の人が言ったように、隣接関係に一般化されたリスト コンテナーを使用することをお勧めします。これは、リンクされたノードまたはノードのベクトルですばやく実装できます。たとえば、Java では、両方を使用しListて実装/プロファイルし、どちらがアプリケーションに最適かを確認します。NBは、 ごとに配列を圧縮します。上記のように償却はありませんが、sは償却されます。LinkedListArrayListArrayListremoveadd

他のバリエーションがあります: 非常に密度の高いグラフがあり、特定のラベルを持つノードの特定のノードに付随するすべてのエッジを頻繁に検索する必要があるとします。次に、キーがエッジ ラベルである隣接関係のマップが必要です。もちろん、マップはハッシュ、ツリー、スキップリストなど、好きなものにすることができます。

リストは続きます。効率的な頂点削除の実装方法は? ご想像のとおり、ここにも代替案があり、それぞれに長所と短所があります。