关联项目分组算法 [英] Algorithm for grouping related items

问题描述

我有一组物品。集合中的每个项目都可以与一个或多个其他项目相关。我想构建一种算法，将直接或通过其他项目关联的项目组合在一起。

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.

示例：
我的集合是{a，b，c，d，e，f}

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

a和b是相关的。

该算法应产生以下组：
{a，b}，{c，d， e}，{f}

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 :-)

推荐答案

使用联盟查找。它的速度非常快。使用路径压缩，复杂度降低为O（a（n）），其中a（n）是Ackermann函数的逆。

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.

这篇关于关联项目分组算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！