la implementación de las discusiones del algoritmo de Kruskal utilización

Question

estoy poniendo en práctica el algoritmo de Kruskal y me gustaría utilizar hilos. Sin embargo no estoy seguro de que sé lo suficiente sobre el algoritmo para hacer esto.

Lo que me imagino es que había diferentes partes del gráfico se resolverían para y se conectan al final. ¿Puede alguien me punto en la dirección correcta? Gracias.

Answer 1

Wikipedia

  

La investigación se ha centrado en la solución de la   problema del árbol de expansión mínimo en una   manera altamente paralelizado. Con un   número lineal de procesadores es   posible resolver el problema de   O (log n) tiempo. Un documento de 2003 "rápido   Memoria compartida-Algoritmos para la Computación   el Bosque de expansión mínimo de escasa   Los gráficos" de David A. Bader y Guojing   Cong demuestra una pragmática   algoritmo que puede calcular MSTs 5   8 veces más rápido en los procesadores de una   optimizado algoritmo secuencial. [9]   Típicamente, algoritmos paralelos son   basado en el algoritmo de Prim-de Boruvka   y especialmente el algoritmo de Kruskal hacer   No escalar, así que adicional   procesadores.

Por lo tanto, es posible mirar en el algoritmo mencionado en dicho papel, pero Kruskal probablemente no se beneficiará de múltiples hilos.

Answer 2

algoritmo de Kruskal para el MST es difícil poner en paralelo porque considera bordes en un orden estrictamente especificado. Usted debe echar un vistazo a algoritmo de Boruvka que es más fácil para paralelizar como se puede trabajar en cada subárbol de un MST parcial independiente.