Motivation
Lección 2 de 9 del curso Algoritmo de Prim - Algoritmos de grafos de Coddy.
Mientras que Kruskal ordena todas las aristas globalmente y utiliza union-find, Prim mantiene un único árbol en crecimiento y busca repetidamente el vértice externo más cercano.
¿Por qué aprender Prim?
- Grafos densos: Prim con las estructuras adecuadas es eficiente cuando hay muchas aristas.
- Propiedad del corte: es una ilustración práctica de por qué la arista más barata que sale del árbol actual siempre es segura de añadir.
- Dos visiones de un mismo problema: comparar Prim y Kruskal profundiza tu comprensión de los árboles de expansión mínima.
Debido a que todos los MST de un grafo comparten los mismos pesos de las aristas, Prim y Kruskal siempre reportan el mismo peso total.
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
