c++ - C ++でグラフを実装する最良の方法は?

Question

一定の、順序付けられていない、重み付けされていない、まばらなグラフを実装しようとしています(つまり、エッジは移動しません)。ただし、多くの頂点スワップ操作を行うことで、頂点の順序が変更されます。

たとえば、1 つの方法は、unordered_sets + 隣接リスト構造のベクトルを使用することです。

0: 1 2 3
1: 0 2
2: 0 1
3: 0

0 と 3 を入れ替えます。

0: 3
1: 3 2
2: 3 1
3: 1 2 0

C++ での最適な実装は何ですか?

Answer 1

Boost Graph Libraryを調べてください。それはおそらくあなたのニーズに合うでしょうが、そうでない場合は、独自のものを作成しようとする前に、ドキュメントが主題について学ぶための良い出発点になるかもしれません.

編集: スパース グラフを使用することを期待している場合、隣接リストバージョンはおそらく最初に調べたい実装です。ブースト adjacency_list グラフのパフォーマンス特性は、それを実装するために使用される基本的なデータ構造を (テンプレート引数を介して) 変更することで微調整できることに注意してください。

編集:あなたが説明している頂点の交換に関しては、おそらくこれを行う最も簡単な方法は、頂点をそのままにしておくことができる頂点タイプを設定することですが、そのプロパティは別のものと簡単に交換できます。Bundled Propertiesメカニズムは、これを実装する 1 つの方法です。

Answer 2

boost::graphおそらく。

いくつかの実装があり、頂点ごとに複数のパラメーターを指定できます。さらなる調査は、学生の演習として残されています。