java - スレッドを利用したクラスカルのアルゴリズムの実装

Question

私はクルスカルのアルゴリズムを実装しており、スレッドを利用したいと考えています。ただし、これを行うためのアルゴリズムについて十分に知っているかどうかはわかりません。

私が想像しているのは、グラフのさまざまな部分が解決され、最後に接続されることです。誰かが私を正しい方向に向けることができますか? ありがとう。

Answer 1

ウィキペディアより

研究は、高度に並列化された方法で最小スパニング ツリー問題を解決することに重点を置いてきました。線形数のプロセッサを使用すると、O(logn) 時間で問題を解決できます。David A. Bader と Guojing Cong による 2003 年の論文「Fast Shared-Memory Algorithms for Computing the Minimum Spanning Forest of Sparse Graphs」では、最適化された逐次アルゴリズムよりも 8 プロセッサで MST を 5 倍高速に計算できる実用的なアルゴリズムが示されています[9]。通常、並列アルゴリズムは Boruvka のアルゴリズムに基づいています。Prim のアルゴリズム、特に Kruskal のアルゴリズムは、プロセッサを追加しても拡張できません。

したがって、その論文で言及されているアルゴリズムを調べることもできますが、Kruskal はおそらく複数のスレッドの恩恵を受けないでしょう。

Answer 2

Kruskal の MST のアルゴリズムは、厳密に指定された順序でエッジを考慮するため、並列化が困難です。Boruvkaのアルゴリズムは、部分 MST の各サブツリーを個別に処理できるため、並列化が容易です。