El Algoritmo de Prim
El algoritmo de Prim es un tipo de algoritmo voraz que se utiliza para el cálculo de árboles de recubrimiento mínimo.
El procedimiento es el siguiente:
- En primer lugar el algoritmo selecciona arbitrariamente un nodo del grafo como raiz del árbol que se va a construir.
- A continuación, en cada paso del algoritmo, se añade al árbol la arista de coste mínimo tal que el árbol más la arista seleccionada sea también un árbol.
- El algoritmo continúa hasta que el árbol tiene n-1 aristas.
A continuación se muestra un ejemplo:
Ejemplos de aplicaciones prácticas:
- Cálculo de la ruta más corta entre ciudades.
- Enrutamiento de redes.
En la sección de visualización podrás conocer cómo funciona. En primer lugar introduce el número de nodos del grafo y pulsa RESET. A continuación rellena la matriz de adyacencia poniendo 1 donde haya enlace entre los nodos y 0 donde no lo haya, y pulsa ACTUALIZAR. A continuación podrás ver la evolución del algoritmo y las estructuras de datos utilizando los botones de control superiores.