用于检测间接图中的循环的最佳并行算法(Best parallel algorithm for detecting cycles in a undirect graph)

用于检测间接图中的循环的最佳并行算法(Best parallel algorithm for detecting cycles in a undirect graph)

我想检测无向图中的循环，以便找到最小生成树（特别是我想使用Kruskal算法）。 由于我想并行化代码，我想知道哪种算法是最好的，深度优先搜索union-find算法？ 谢谢你的任何建议。

I want to detect cycles in an undirected graph such that I can find the minimum spanning tree (in particular I want to use Kruskal algorithm). Since I want to parallelize the code, I was wondering which algorithm is the best, Depth-first search of union-find algorithm? Thanks for any suggestions.

最满意答案

在所有三种MST算法中，只有Boruvka的 MST算法易于并行化，而kruskal和prims是顺序贪心算法，因此并行实现它们的范围最小。

注意：实现高效并行boruvka的研究课题可能会找到一些论文

Of all three MST algorithms only Boruvka's MST algorithm is easily parallelizable whereas the kruskal and prims are sequential greedy algorithms hence there is minimum scope for parallel implementation of them.

Note: It is a research topic to achieve efficient parallel boruvka might find some papers