グループ分けの方法

グループ分けを行うプログラムを考えています．
具体的には，

A,B,C,D,Eがあったとき，
A-B，A-C，B-Dが1つのグループ（ペア）であれば，
A-B-C-Dを１つのグループ（群）とする．

このようなルールのもとで，グループ分けをおこないたいのですが，
どのようにしたらよいものかいい考えが浮かんできません．

なお，元データはそれぞれのペアが1行に1つずつあります．

A B
A C
B C
B D
: :
: :

どなたか良い考えが思いつかれた方がいれば，
些細なことでも結構ですので御教授よろしくお願いします．

No.2 回答者： Tacosan 回答日時： 2009/05/25 10:38

う～ん, どこで悩んでいるかが分かればなぁ....

基本的にはアルゴリズムをそのまま実装するだけでいいです. ただし, 本当にそのまま実装するととてつもなく効率が悪くなる可能性があるのでその辺はちょっと考える:
1. 入力ータをグラフと思って隣接リストにする
2. すべての要素のグループを空にする
3. until すべての要素にグループが割り当てられる do
4. グループが割り当てられていない要素を 1つ見つける
5. その要素を始点として幅優先探索でも深さ優先探索でも好きな方で探索する
6. 探索中に見つかったすべての要素を始点と同じグループに割り当てる
7. end until
要素数を n, ペアの数を m とすると, よほど下手に組まない限り O(n^2+m) より悪くはできないはず. ちょっと頭を使えば O(n+m).

この回答へのお礼

Tacosan さん

　ありがとうございます．
　とりあえず四苦八苦しながらではありますがやってみます．

お礼日時：2009/05/26 20:30

No.1 回答者： Tacosan 回答日時： 2009/05/24 21:23

グラフを連結成分に分割しろ, ってことだよね?

素直に
「X-Y というペアがあって X がグループ a に入っていたら Y もグループ a に入れる」
というのをひたすら繰り返すだけでいいのでは?
特に悩むことはないと思いますが.

この回答へのお礼

その通りなんですが・・・
どういう風にプログラムを書けばよいかを悩んでまして・・・

お礼日時：2009/05/25 07:14