El Algoritmo de Kruskal
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:
- Partimos del conjunto de aristas AR vacío.
- A continuación, en cada paso del algoritmo, se añade a AR la arista más corta disponible que aún no haya sido añadida a AR ni rechazada.
- En los pasos intermedios, el grafo constará de varias componentes conexas.
- Al final del algoritmo, el grafo contendrá una única componente conexa.
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.