c++ - サイズが不明な無向グラフの C++ データ構造

Question

サイズが不明な無向グラフを探索し、隣接リストを作成するプログラムを作成しようとしています。通常はset<set<String>>(部屋は文字列で識別されます) を作成しますが、これは C++ では不安定だと言われました。より良いデータ構造は何でしょうか?

Answer 1

後で情報を照会する方法によって異なります。

2 つの選択肢を提案できます。

using namespace std;
set< pair<string,string> >

また

using namespace std;
multimap<string,string>

最初のケースsetでは、2 つのノードが接続されているかどうかを確認できますが、クエリを実行するには両方のノード (A と B) を知る必要があります。2 番目のケースmultimapでは、ノード A を指定すると、隣接するすべてのノードを持つ反復子を簡単に取得できます。

ペアを 2 回挿入するか、常に辞書順にエッジを追加するなどの規則を使用する必要があります。