Umsetzung Kruskals Algorithmus unter Verwendung von Threads

Question

Ich bin der Umsetzung Kruskals Algorithmus und ich möchte Threads verwenden. Allerdings bin ich nicht sicher, ob ich genug über den Algorithmus wissen, dies zu tun.

Was ich mir vorstellen, dass ich verschiedene Teile des Graphen würde wäre gelöst werden und am Ende verbunden. Kann jemand mich in die richtige Richtung? Danke.

Answer 1

Wikipedia

  

Die Forschung hat sich auf die Lösung der Schwerpunkt   Minimum Spanning-Tree-Problem in einem   sehr Art und Weise parallelisiert. Mit einem   lineare Anzahl von Prozessoren ist   möglich, das Problem zu lösen in   O (logn) Zeit. A 2003 Papier „Fast   Shared-Memory-Algorithmen für Computing   das Minimum Spanning Wald von Sparse   Graphs“von David A. Bader und Guojing   Cong zeigt eine pragmatische   Algorithmus, der 5 MSTs berechnen kann,   mal schneller auf 8 Prozessoren als ein   optimierte sequentieller Algorithmus. [9]   Typischerweise parallele Algorithmen sind   basierend auf Boruvka Algorithmus-Prim   und vor allem Kruskals Algorithmus tun   auch nicht zu zusätzlichen maßstabs   Prozessoren.

So könnten Sie den Algorithmus in diesem Papier erwähnt schauen, aber Kruskal wahrscheinlich von mehreren Threads nicht profitieren.

Answer 2

Kruskals Algorithmus für MST ist schwer zu parallelisieren, weil es Kanten in einer streng festgelegten Reihenfolge berücksichtigt. Sie sollten einen Blick auf Borůvka des Algorithmus, der parallelisieren leichter ist als es kann unabhängig auf jedem Unterbaum einen Teil MST arbeiten.