c++ - 隣接リストを実装するためのハッシュマップ

Question

ベクトルのベクトルのn番目の要素がノードnのフレンドリストを参照する、ベクトルのベクトルアプローチを使用して隣接リストを実装しました。

ハッシュマップのデータ構造がもっと役立つのではないかと思っていました。それらの違いを単純に識別できないため、まだためらいがあります。たとえば、n番目の要素の隣接要素（検索、削除）で操作をチェックして実行したい場合、ベクトルのベクトルアプローチよりも効率的である可能性があります。

Answer 1

vector<vector<ID>>ノードのセットが固定されている場合は、Aが適切なアプローチです。ただし、突然ノードを削除することにした場合は、イライラします。ノードの後に​​格納されている要素が置き換えられ、参照が失われるため、ベクトルを縮小することはできません。一方、無料の（再利用可能な）IDのリストを横に置いておけば、スロットを「無効化」して後で再利用できます。非常に効率的です。

Aunordered_map<ID, vector<ID>>を使用すると、ノードをはるかに簡単に削除できます。先に進んで、新しく作成されたノードに新しいIDを割り当てることができ、空のスロットが失われることはありません。特に衝突ではそれほどコンパクトではありませんが、それほど悪くはありません。古いコンパイラでベクトルを移動する必要がある場合、再ハッシュの速度が低下する可能性があります。

最後に、aunordered_multimap<ID, ID>はおそらく管理が最も簡単なものの1つです。それはまた、記憶を風にまき散らします、しかしねえ:)

個人的には、aを使用してプロトタイピングを開始unordered_multimap<ID, ID>し、ニーズに対して遅すぎることが判明した場合にのみ、別の表現に切り替えます。

(x, y)注：隣接関係が対称である場合は、関係が保存される場合よりも確立することで、ノード数を半分に減らすことができますmin(x, y)。

Answer 2

ベクトルのベクトル

ベクトルのベクトルは、エッジを削除する必要がない場合に適したソリューションです。

O（1）でエッジを追加したり、O（N）でネイバーを反復処理したりできます。エッジを削除することはできますがvector[node].erase(edge)、遅くなり、複雑さはO（頂点の数）のみになります。

ハッシュマップ

ハッシュマップをどのように使用したいかわかりません。エッジの挿入が設定を意味する場合hash_map[edge] = 1は、ノードの隣接ノードを反復処理できないことに注意してください。