algorithm - 並列の最小スパニングツリーアルゴリズム

Question

私はいくつかの最小スパニングツリーアルゴリズムを知っています：Boruvka、Prim、Kruskal。並列に実装できるのはどれですか？

ありがとう！

Answer 1

これらの3つのアルゴリズムのうち、Boruvkaアルゴリズムのみを簡単に並列化できる可能性があります。

algoritmy.netのBoruvkaアルゴリズムの説明からの引用：

Borůvkaのアルゴリズムの重要な利点は、各コンポーネントの最も安価な出力エッジの選択が他のコンポーネントによる選択とは完全に独立しているため、簡単に並列化できることです。