kruskal - prim algorithm

¿Cómo implementar el algoritmo de Prim con un montón de Fibonacci? (3)

El algoritmo de Prim selecciona el borde con el peso más bajo entre el grupo de vórtices ya seleccionados y el resto de los vórtices.
Así que para implementar el algoritmo de Prim, necesitas un montón mínimo. Cada vez que seleccionas un borde, agregas el nuevo vórtice al grupo de vórtices que ya has elegido, y todos sus bordes adyacentes entran en el montón.
A continuación, elige el borde con el valor mínimo de nuevo desde el montón.

Así que los tiempos que obtenemos son:
Fibonacci:
Elección de borde mínimo = O (tiempo de eliminación mínimo) = O (registro (E)) = O (registro (V))
Inserción de bordes en el montón = O (tiempo de inserción del elemento en el montón) = 1

Mínimo montón
Elegir el borde mínimo = O (tiempo de quitar el mínimo del montón) = O (registro (E)) = O (registro (V))
Insertar bordes en el montón = O (tiempo de inserción del elemento en el montón) = O (registro (E)) = O (registro (V))

(Recuerde que E = ~ V ^ 2 ... así que log (E) == log (V ^ 2) == 2Log (V) = O (log (V))

Entonces, en total tienes inserciones E, y V selecciones mínimas (es un árbol al final).

Así que en Min heap obtendrás:

O (Vlog (V) + Elog (V)) == O (Elog (V))

Y en el montón de Fibonacci obtendrás:

O (Vlog (V) + E)

Conozco el algoritmo de Prim y su implementación, pero siempre me salto una parte que quiero preguntar ahora. Se escribió que la implementación del algoritmo de Prim con Fibonacci Heap es O(E + V log(V)) y mi pregunta es:

¿Qué es un montón de Fibonacci en breve?
¿Cómo se implementa? Y
¿Cómo se puede implementar el algoritmo de Prim con un montón de Fibonacci?

Implementé Dijkstra utilizando montones de Fibonacci hace unos años, y el problema es bastante similar. Básicamente, la ventaja de los montones de Fibonacci es que hace que encontrar el mínimo de un conjunto sea una operación constante; así que eso es muy apropiado para Prim y Dijkstra, donde en cada paso tiene que realizar esta operación.

Porque es bueno

La complejidad de esos algoritmos que usan un montón binomial (que es la forma más "estándar") es O (E * log V), porque, aproximadamente, probará cada borde (E), y para cada uno de ellos agregará El nuevo vértice a su montón binomial (registro V) o disminuir su clave (registro V), y luego tiene que encontrar el mínimo de su montón (otro registro V).

En cambio, cuando usa un montón de Fibonacci, el costo de insertar un vértice o disminuir su clave en su montón es constante, por lo que solo tiene una O (E) para eso. PERO eliminar un vértice es O (log V), por lo que al final se eliminará cada vértice que agregue un O (V * log V), para un total de O (E + V * log V).

Entonces, si su gráfica es lo suficientemente densa (por ejemplo, E >> V), usar un montón de Fibonacci es mejor que un montón binomial.

Cómo

Por lo tanto, la idea es utilizar el montón de Fibonacci para almacenar todos los vértices accesibles desde el subárbol que ya construyó, indexado por el peso del borde más pequeño que conduce a él. Si entendió la implementación o el algoritmo de Prim con el uso de otra estructura de datos, no hay ninguna dificultad real para usar un montón de Fibonacci en su lugar, solo use los métodos de insertar y deleteminar del montón como lo haría normalmente, y use el método de disminución de tecla para actualizar un vértice cuando sueltas un borde que conduce a ella.

La única parte difícil es implementar el montón de Fibonacci real.

No puedo darles todos los detalles de implementación aquí (eso llevaría páginas), pero cuando hice la mía, me apoyé en gran medida en la Introducción a los algoritmos (Cormen et al) . Si aún no lo tiene, pero está interesado en los algoritmos, le recomiendo que obtenga una copia. Es independiente del lenguaje y proporciona explicaciones detalladas sobre todos los algoritmos de estándares, así como sus pruebas, y definitivamente mejorará su conocimiento y capacidad para usarlos todos, y diseñar y probar nuevos. Este PDF (de la página de Wikipedia que has vinculado) proporciona algunos de los detalles de la implementación, pero definitivamente no es tan claro como Introducción a los algoritmos .

Tengo un report y una presentation que escribí después de hacer eso, que explican un poco cómo proceder (para Dijkstra - vea el final del ppt para las funciones del montón de Fibonacci en pseudo-código) pero todo está en francés ... y mi code está en Caml (y en francés), así que no estoy seguro de si eso ayuda. Y si puedes entender algo de eso, por favor sé indulgente, estaba empezando a programar, por lo que mis habilidades de codificación eran bastante deficientes en ese momento ...

Un montón de Fibonacci es una cola de prioridad bastante compleja que tiene un excelente comportamiento asintótico en todas sus operaciones: inserción, encontrar y min. Todo funciona en O (1) tiempo amortizado, mientras que eliminar y extraer-min se ejecutan en O amortizado (lg n) tiempo. Si desea una buena referencia sobre el tema, le recomiendo encarecidamente que elija una copia de "Introduction to Algorithms, 2nd Edition" de CLRS y que lea el capítulo al respecto. Es notablemente bien escrito y muy ilustrativo. El documento original sobre los montones de Fibonacci de Fredman y Tarjan está disponible en línea, y es posible que desee verlo. Es denso, pero da un buen tratamiento del material.

Si desea ver una implementación de los montones de Fibonacci y el algoritmo de Prim, tengo que dar un complemento descarado para mis propias implementaciones:

Los comentarios en ambas implementaciones deben proporcionar una descripción bastante buena de cómo funcionan; ¡Hazme saber si hay algo que pueda hacer para aclarar!