algorithm - 猪中的连通分量算法

Question

我们四处寻找一种简单的算法来找到直径有时很大的图中的连通分量（最大的分量有时可以达到 1m）。

我们发现了很多非常复杂的 MR 算法：

• http://codingwiththomas.blogspot.de/2011/04/graph-exploration-with-hadoop-mapreduce.html
• http://blog.piccolboni.info/2010/07/map-reduce-algorithm-for-connected.html
• http://chasebradford.wordpress.com/2010/10/23/mapreduce-implementation-for-union-find/

一个非常简单的算法有什么问题：

• foreach 组件，生成 flatten(nodes_bag) 作为节点，node_with_the_smallest_id 作为 comp_id；
• 按节点分组
• 过滤具有多个comp_id的节点，并构建“将大comp_id更新为小comp_id”表
• 将所有comp_id大的节点更新为对应的新的小comp_id，并将它们标记为脏

并继续使用这些脏节点进行下一次迭代......我们在这里缺少什么？

Answer 1

你提出的算法不是二次的吗？Tarjan 的连通分量算法是线性的。

Answer 2

好的。我们不能使用这个非常简单的算法的原因是它有一个错误 = 构建“将大 comp_id 更新为小 comp_id”阶段可能是递归的。例如，当上一次迭代中有 3 个组件时：

A->{1,2}
B->{2,3}
C->{3,4}

group by 和 filter 将为我们构建这个转换表：

A->B
B->C

这会导致迭代次数在某些情况下是线性的（最大直径）=像这个迷你示例中的长链需要很长时间才能收敛。