Q

用於檢測不連續圖中的週期的最佳並行算法

2014-02-09 33 views 0 likes

0

我想檢測無向圖中的週期，以便能夠找到最小生成樹（特別是我想使用Kruskal算法）。由於我想並行化代碼，我想知道哪種算法是最好的，聯合發現算法的深度優先搜索？感謝您的任何建議。用於檢測不連續圖中的週期的最佳並行算法

2014-02-09 Betelgeuse

+0

@Betelqeuse克魯斯卡貪婪算法，其中成本較低的邊緣人之前認爲因此，我不認爲有什麼方法可以並行化。 –

+0

所以只有Prim可並行化？你知道其他算法嗎？ – Betelgeuse

A

回答

1

在所有三種MST算法中只有Boruvka's MST算法很容易並行化，而kruskal和prim是順序貪婪算法，因此它們的並行實現有最小範圍。

注：這是一個研究課題，以實現高效的並行boruvka可能會發現一些文件

2014-02-09 13:40:44

相關問題