attuazione algoritmo che utilizza le discussioni di Kruskal

Question

sto implementando l'algoritmo di Kruskal e mi piacerebbe utilizzare fili. Comunque io non sono sicuro io conosco abbastanza l'algoritmo per farlo.

Quello che immagino è che mi piacerebbe diverse parti del grafico sarebbe risolto per e collegati alla fine. Qualcuno mi può punto nella giusta direzione? Grazie.

Answer 1

Wikipedia

  

La ricerca si è concentrata sulla soluzione del   di copertura minimo problema albero in un   modo altamente parallelo. Con un   numero lineare di processori è   possibile risolvere il problema in   O (log n) tempo. Un documento 2003 "Veloce   Shared-Memory algoritmi per il calcolo   Spanning Foresta minimo di Sparse   Grafici" di David A. Bader e Guojing   Cong dimostra una pragmatica   algoritmo in grado di calcolare MST 5   volte più veloce su 8 processori di un   ottimizzato algoritmo sequenziale. [9]   Tipicamente, gli algoritmi paralleli   sulla base dell'algoritmo-Prim di Borůvka   e in particolare l'algoritmo di Kruskal fare   non scala anche per ulteriori   processori.

Quindi, si potrebbe esaminare l'algoritmo indicato in tale documento, ma Kruskal probabilmente non potranno beneficiare di più thread.

Answer 2

Algoritmo di Kruskal per MST è difficile da parallelizzare perché considera bordi in ordine strettamente specificato. Si dovrebbe dare un'occhiata a algoritmo di Boruvka che è più facile per parallelizzare come può funzionare su ogni sottostruttura di un MST parziale indipendente.