私は一連のアイテムを持っています。セット内の各アイテムは、1つ以上の他のアイテムに関連付けることができます。私は、関連する項目を直接または他の項目を通じてグループ化するアルゴリズムを構築したいと考えています。関連アイテムをグループ化するためのアルゴリズム
例： 私のセットは、{A、B、C、D、Eは、F}
とBが関連しています。 cはdに関連し、dはeに関連する。
アルゴリズムは、次のグループを生成しなければならない： {A、B}、{C、D、E}、{F}
効率的なアルゴリズムの任意のアイデアをこれを行うために？ありがとうございます:-)
Union Findをご利用ください。信じられないほど速いです。パス圧縮を使用すると、複雑さは、a（n）がAckermann関数の逆数である場合、O（a（n））に減少する。
F
、B、C、D、E、および関係のリスト：ビットに答えるst0le年代に拡大すること
素晴らしい。この下限の証明を見たくない。 –
本当にありがとうございます！ :) – st0le
さて、私はTarjanを読んですぐに_the_ Lengauer-Tarjanアルゴリズムを考えました。それらの過去のコンパイラコースのすべてのメモリは戻ってきていました:) –
...
は、だから、要素のリストを持っています：
AB
CD
デ
初期EACを配置することにより、 h要素をそれ自身のグループに含める。
次に、リレーションのリストを繰り返します。各関係について
、各要素がメンバーであるグループを見つけ、これらのグループを統一。この例ではそう
：
1: init -> {a}, {b}, {c}, {d}, {e}, {f}
2: a-b -> {a,b}, {c}, {d}, {e}, {f}
3: c-d -> {a,b}, {c,d}, {e}, {f}
4: d-e -> {a,b}, {c,d,e}, {f}
あなたは明らかあなたの関係のすべてを確認する必要があります。実装方法によっては、アルゴリズムの効率性に影響を与えます。だから本当にあなたは要素のグループのセットで要素を見つける最も速い方法が何であるかを知りたがっています。素朴なアプローチはO（n）でこれを行います。これを改善するには、特定の要素がどのグループに属しているかを記録します。次に、2つのグループを結合するときは、レコードを更新する必要があります。小規模なグループを大規模なグループにまとめることができるため、更新する必要があるレコードの数を節約できます。
は、「b」に関連する「a」を意味し、「a」に関連する「b」を暗示しますか？ – st0le
はい、そうです。多分私が使った "関係"という言葉は不十分ですか？ –
私の答えは成立する。 – st0le