关联项目分组算法 [英] 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屋!