Algoritmo de Kruskal
Kruskal's algorithm
- Fecha
- 1956 · fiabilidad alta
- Lugar
- Bell Telephone Laboratories, Murray Hill, Nueva Jersey, Estados Unidos
- Autoría
- Joseph Kruskal
- Ámbito
- Saber y símbolos
Qué se descubrió
Kruskal publicó un algoritmo voraz que halla el árbol de expansión mínima de un grafo con pesos: ordena las aristas por peso y las añade una a una evitando ciclos. Es uno de los algoritmos de grafos más usados en diseño de redes.
Loberman y Weinberger redescubrieron el mismo algoritmo de forma independiente en 1957.
A qué dio paso
- Optimización de redes de telecomunicaciones y transporte
- Uso de estructuras de conjuntos disjuntos (union-find)
- Base de algoritmos posteriores de grafos