Algoritmo de Prim

Algoritmo de Prim#

Idea general#

  • Inicia desde cualquier vértice y va creciendo un árbol:

    • En cada paso añade la arista de menor peso que conecta un vértice dentro del árbol con uno fuera del árbol (evitando ciclos).

  • Finaliza cuando se han añadido \(n-1\) aristas (siendo \(n\) el número de vértices).

Pseudocódigo (boceto)#

Prim pseudo

Consideraciones#

  • Si hay empates de peso, la elección de la arista no está determinada; para hacerlo determinista, ordena previamente las aristas por peso (y por un criterio secundario reproducible).

  • Puede haber más de un MST en un grafo simple, conexo y ponderado.

Ejemplo de seguimiento#

Grafo inicial Evolucion MST

Prim con cola de prioridad#

Prim colaPrioridad

Más pasos del ejemplo#

Ejemplo 1 Ejemplo 2 Ejemplo 3 Ejemplo 4 Ejemplo 5 Ejemplo 6 Ejemplo 7

Contents