Algorithm for grouping related items

Question

I have a set of items. Each item in the set can be related to one or more other items. I would like to build an algorithm that group items that are related together, either directly or through other items.

Example : My set is {a, b, c, d, e, f}

a and b are related. c is related to d and d is related to e.

The algorithm should produce the following groups : {a, b}, {c, d, e}, {f}

Any ideas of an efficient algorithm for doing this ? Thanks in advance :-)

Answer 1

Use Union Find. It's incredibly fast. Using path compression, the complexity reduces to O(a(n)) where a(n) is the inverse of the the Ackermann function.

Answer 2

To expand on st0le's answer a bit...

So you have a list of elements:

a, b, c, d, e, f

And a list of relations:

a-b
c-d
d-e

Initialize by placing each element in its own group.

Then, iterate over your list of relations.

For each relation, find the group that each element is a member of, and then unite those groups.

So in this example:

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}

You will obviously have to check all of your relationships. Depending on how you implement the 'find' part of this will impact how efficient your algorithm is. So really you want to know what is the quickest way to find an element in a set of groups of elements. A naive approach will do this in O(n). You can improve upon this by keeping a record of which group a given element is in. Then, of course, when you unite two groups, you will have to update your record. But this is still helpful because you can unite the smaller group into the larger group, which saves on how many records you need to update.