Algorithm for grouping related items

Question

I have a set of elements. Each element in the set can be associated with one or more other elements. I would like to build an algorithm that groups elements connected to each other, either directly or through other elements.

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

a and b are connected. c is associated with d and d is associated with e.

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

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

Answer 1

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

Answer 2

To expand on st0le answer a little ...

So you have a list of items:

a, b, c, d, e, f

And a list of relationships:

a-b
c-d
d

Initialize by placing each item in its group.

Then iterate over the list of your relationships.

For each relationship, find the group in which each member is a member, and then combine these groups.

So in this example:

1: init -> {a}, {b}, {c}, {d}, {e}, {f} 2: ab -> {a,b}, {c}, {d}, {e}, {f} 3: cd -> {a,b}, {c,d}, {e}, {f} 4: de -> {a,b}, {c,d,e}, {f} 

Obviously, you have to check all your relationships. Depending on how you implement “finding,” part of this will affect the performance of your algorithm. So what you really want to know is the fastest way to find an element in a set of element groups. A naive approach will do this in O (n). You can improve this by keeping a record of which group this item is in. Then, of course, when you combine the two groups, you will need to update your record. But this is still useful because you can combine a smaller group into a larger group, which saves on how many records you need to update.