グラフパーティションのデータグループ化ノードを保存する必要があります。
[node1、node2] [node3] [node4、node5、node6]
私の最初のアイデアは、単純なベクトルまたはintの配列を作成することでした。配列内の位置は、node_idを示し、その値は、ある種のgroup_idです。
問題は、多くのパーティションアルゴリズムがグループ内のノードのペアでの動作に依存していることです。この方法では、どのノードが同じグループに属しているかを見つけるために、ベクトルを検索するために多くの計算を無駄にするだろうと思います。
パーティションの数学的定義に近いように見えるセットのstlセットとして保存することもできますが、ネストされたセットはアドバイスされていないか不要であるという印象を受けており、よくわからない内部セットを変更する必要があります可能です。
助言がありますか？
セットで正確に何をしたいかによっては、ばらばらなセットデータ構造を試すことができます。この構造では、各要素には、findそれが属するセットの「代表」を返すメソッドがあります。
C++ 実装はBoostで利用できます。
頭に浮かぶ優れたデータ構造が 2 つあります。
最初のデータ構造 (およびここで以前に言及されたもの) は素集合フォレストであり、「これら 2 つの集合をマージする」および「x はどの集合にあるのか?」の非常に効率的な実装を提供します。ただし、グループを互いに分離する操作はサポートしていません。
私がお勧めするもう 1 つの構造は、リンク/カット ツリーです。この構造により、ツリーに結合できるグラフのパーティションを構築できます。互いに素なセット フォレストとは異なり、パーティションを記述するツリーは小さなツリーに分割できるため、パーティションを小さなグループに分割できます。この構造は、union/find 構造よりも効率が少し劣りますが、償却済み O(lg n) のすべての操作をサポートしています。