適切なデータ構造（グラフ）パーティション

Question

Iグラフパーティションのノードをグループ化するデータを格納する必要がある、のようなもの：

[ノード1、ノード2] [ノード3] [ノード4、NODE5、node6]

私の最初のアイデアは、配列の位置がnode_idであり、値がgroup_idである単純なベクトルまたは配列を持つことでした。

多くのパーティションアルゴリズムは、グループ。この方法では、どのノードが同じグループに属しているかをベクトルで調べるために多くの計算を浪費すると思います。

私はパーティションの数学的な定義に近いと思われるセットのstlセットとしても格納できますが、ネストされたセットはアドバイスされているか不要であるという印象を受けています。私は確信が持てません。

提案がありますか？

Answer 1

セットで何をしたいのかによって、disjoint set data structureを試すことができます。この構造では、各要素には、それが属するセットの「代表」を返すメソッドfindがあります。

BoostでC++の実装を利用できます。

Answer 2

2つの良いデータ構造があります。

第1のデータ構造（およびこれまでに言及したもの）は、「これらの2つのセットをマージする」および「どのセットにxがあるか」という非常に効率的な実装を提供する独立したセットのフォレストです。ただし、グループを互いに分離して操作することはサポートしていません。

他の構造は、リンク/カットツリーです。この構造を使用すると、ツリーにまとめて結合できるグラフのパーティションを構築できます。分離された集合フォレストとは異なり、パーティションを記述するツリーをより小さなツリーに分割することができ、パーティションを小さなグループに分割することができます。この構造体はunion/find構造体よりも効率が少し劣りますが、償却されたO（lg n）のすべての演算をサポートしています。