Consulta sobre implementación de el Algoritmo Prim

Consulta sobre implementación de el Algoritmo Prim

de Jeronimo Jacques Balma -
Número de respuestas: 3

Buenas, tenia una consulta sobre la implementación de el algoritmo Prim de las diapositivas.

Mi duda era si las aristas del árbol de cubrimiento no deberían ser guardadas en un conjunto a parte a retornar, o si esto no es necesario. Y si es necesario, cuando deberíamos de añadir una arista y cuando no?, se me ocurren algunas soluciones pero no se si están bien.

Gracias

En respuesta a Jeronimo Jacques Balma

Re: Consulta sobre implementación de el Algoritmo Prim

de Fernando Fernandez -
Hola Jeronimo.
¿Te referís a https://eva.fing.edu.uy/pluginfile.php/489568/mod_resource/content/1/04mst_TeoTarde.pdf?
Lo que se muestra ahí es un marco genérico que uno adapta a lo que se necesita. Tal vez alcance con obtener el costo del árbol, o tal vez se necesite el árbol en sí mismo. En este caso sí hay que registrar de alguna manera las aristas. ¿Qué solución te parece que sirve?
En respuesta a Fernando Fernandez

Re: Consulta sobre implementación de el Algoritmo Prim

de Jeronimo Jacques Balma -
Si me refiero a esa. Lo que a mi se me ocurrió fue ir guardando la última arista por la que fue actualizado cada nodo de la cola de prioridad y cuando este nodo es eliminado de la cola se agrega la arista a la solución, pero no se si hay alguna forma mas eficiente o esa forma directamente no funciona.