算法将相关项目

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

实施例： 我的集合为{A，B，C，d，E，F}

a和b是相关的。 c与d有关，d与e有关。

该算法应该产生下列基团： {A，B}，{C，d，E}，{F}

这样做的高效算法的任何想法？在此先感谢:-)

来源

2012-03-29 Super Chafouin

不'了'与'B'，暗示有关''了'B'？ – st0le 2012-03-29 04:18:38

是的，它的确如此。也许我用的“关系”这个词是不够的？ – 2012-03-29 04:23:54

太好了。我的答案成立。 – st0le 2012-03-29 04:24:27

使用Union Find。速度非常快。使用路径压缩，复杂度降低为O（A（N）），其中A（n）是阿克曼函数的逆。

来源

2012-03-29 04:20:54 st0le

令人惊叹。不想看到这个下限的证明。 – 2012-03-29 04:53:16

它确实是！ :) – st0le 2012-03-29 05:28:14

好吧，我读了Tarjan，马上想到了Lengauer-Tarjan算法，并且那些过去的编译器课程的所有内存都闪回了:) – 2012-03-29 08:14:32

要扩大st0le的回答有点...

所以，你必须元素的列表：

A，B，C，d，E，F

和联系列表：

AB
CD
德

初始化通过将EAC h元素在它自己的组中。

然后，遍历您关系的列表。

对于每个关系，发现每个元素是一个成员，然后团结的那些基团的基团。

所以在这个例子：

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}

你会明显要检查所有的关系。取决于你如何实现'find'部分会影响算法的效率。所以你真的想知道在一组元素中找到元素的最快捷方式是什么。一种天真的方法将在O（n）中做到这一点。您可以通过保持一个记录哪个组给定的元素是在这个提高。然后，当然，当你团结两组，你将不得不更新您的记录。但这仍然有帮助，因为您可以将较小的组合并成较大的组，从而节省您需要更新的记录数量。

来源

2012-03-29 04:46:22 soundslikeneon

算法将相关项目

回答

相关问题