クラスカル法利用のスレッドを実行します

Question

私は、クラスカルのアルゴリズムを実装していると私はスレッドを利用したいと思います。しかし、私はこれを行うためのアルゴリズムについて十分に知っていることを確認していない。

私は何を想像すると、私はグラフの異なる部分が解かと終わりに接続されることになるだろうとあります。誰もが正しい方向に私を指すことができますか？おかげます。

Answer 1

ウィキペディアする

から

  

研究が解決することに焦点を当てています   最小スパニングツリー問題   非常に並列化された方法。とともに   それは、プロセッサのリニア番号   で、問題を解決することができます   O（LOGN）時間。高速2003紙」   コンピューティングのための共有メモリアルゴリズム   スパースの最小全域森   デビッド・A・ベイダーとGuojingによってグラフ」   コングは、実用的に示しています   MSTS 5を計算することができアルゴリズム   より8つのプロセッサ上に高速回   最適化された逐次アルゴリズム[9]。   典型的には、並列アルゴリズムであります   Boruvkaのアルゴリズム-プリムさんに基づきます   特にクラスカル法を行います   追加にも同様にスケールしませ   プロセッサます。

だから、あなたがその論文で述べたアルゴリズムに見えるかもしれませんが、クラスカルはおそらく複数のスレッドから利益を得ません。

Answer 2

MSTのためのクラスカル法は、それが厳密に指定された順序でエッジを考慮するため並列化するのは難しいです。あなたはのように並列化が容易である Boruvkaののアルゴリズムを見てみる必要がありますそれは独立して、部分的MSTの各サブツリー上で動作することができます。