la mise en œuvre algorithme de Kruskal utilisant les fils

Question

Je suis mise en œuvre de l'algorithme de Kruskal et je voudrais utiliser des fils. Cependant, je ne suis pas sûr que je sais assez sur l'algorithme de le faire.

Ce que j'imagine que j'avais différentes parties du graphique seraient résolus et connectés à la fin. Est-ce que quelqu'un peut-il me montrer la bonne direction? Merci.

Answer 1

De Wikipedia

  

La recherche a mis l'accent sur la résolution de la   problème de l'arbre couvrant minimal dans un   manière très parallélisé. Avec un   nombre linéaire de processeurs, il est   possible de résoudre le problème   O (log n) fois. Un document 2003 « Fast   Partagée-mémoire Algorithmes pour le calcul   Spanning minimum Forêt de Sparse   Graphiques » par David A. Bader et Guojing   Cong démontre une approche pragmatique   algorithme qui peut calculer MST 5   8 fois plus rapide sur les processeurs d'une   algorithme séquentiel optimisé. [9]   En règle générale, les algorithmes parallèles sont   basé sur l'algorithme de son-Prim Borůvka   et surtout l'algorithme de Kruskal faire   pas l'échelle aussi bien à plus   processeurs.

Alors, vous pouvez regarder dans l'algorithme mentionné dans ce document, mais Kruskal ne bénéficiera probablement pas de plusieurs threads.

Answer 2

L'algorithme de Kruskal pour MST est difficile à paralléliser car elle considère les bords dans un ordre strictement spécifié. Vous devriez jeter un oeil à algorithme de Boruvka qui est plus facile à paralléliser comme il peut fonctionner sur chaque sous-arbre d'une manière indépendante MST partielle.