連接組件算法豬

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 

，這將導致迭代次數是線性（最大直徑）在某些情況下=像這個小例子那樣的長鏈會花費很長時間來收斂。