グループ分けの方法

質問

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

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

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

お礼

Tacosan さん

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

回答No.1

Tacosan

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

お礼

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