Kruskal's algorithm
Algoritmo de Kruskal
- Date
- 1956 · confidence high
- Place
- Bell Telephone Laboratories, Murray Hill, New Jersey, United States
- Credited to
- Joseph Kruskal
- Field
- Knowledge & symbols
What was discovered
Kruskal published a greedy algorithm that finds the minimum spanning tree of a weighted graph: it sorts edges by weight and adds them one by one while avoiding cycles. It is one of the most widely used graph algorithms in network design.
Loberman and Weinberger independently rediscovered the same algorithm in 1957.
What it led to
- Optimization of telecommunication and transport networks
- Use of disjoint-set (union-find) data structures
- Basis for later graph algorithms