Kruskal's algorithm
An algorithm that builds a minimum spanning tree by sorting all edges by weight and adding each one unless it would create a cycle.
In more detail
Union-find answers "are these two vertices already connected?" in near-constant time, so sorting dominates the cost at O(E log E). It builds a forest of pieces that merge until V minus one edges connect everything. It suits sparse graphs given as edge lists.
Related terms
- minimum spanning tree — The spanning tree of a weighted, connected graph whose edges have the smallest possible total weight.
- union-find — A data structure that tracks which items belong to the same group, supporting "find the group of x" and "merge the groups of x and y".
- Prim's algorithm — An algorithm that builds a minimum spanning tree by growing it from one start vertex, always adding the cheapest edge leading out of the tree.
- greedy algorithm — An algorithm that builds a solution step by step, always taking the choice that looks best right now and never revisiting it.
Taught in
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers