Prim's和Boruvka的最小生成樹算法

Question

我必須在無向圖中找到最小生成樹，我想並行化代碼。我讀到Boruvka的算法比Kruskal或Prim的算法更容易並行化。儘管如此，通過將Prim算法與Borůvka's算法結合，可以獲得快速並行算法。 我不明白如何將Prim的算法和Boruvka的算法結合起來，有人能幫助我嗎？ 謝謝

Answer 1

如果按照維基百科的鏈接，這種說法，你可以得到的文件描述它 - http://www-static.cc.gatech.edu/~bader/papers/MST-JPDC.pdf

第4節的過程中，他們似乎從不同的起始頂點並行基本運行普里姆「壓縮「每個子樹到超級頂點，並遞歸重新運行，直到這些不能再連接。