连接组件算法猪

Question

我们环顾四周寻找一个简单的算法来找到直径有时很大（最大的组件有时可达到1米）的图中的连接组件。

我们发现很多非常复杂的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} 

集团通过和过滤器将建立我们这个翻译表：

A->B 
B->C 

，这将导致迭代次数是线性（最大直径）在某些情况下=像这个小例子那样的长链会花费很长时间来收敛。