Kruskal's algorithm

Kruskal's algorithm finds a minimum spanning tree by repeatedly adding the lightest edge that connects two different components, stopping when all vertices are connected.

Minimum spanning tree: A spanning tree of a connected weighted graph whose total edge weight is no greater than that of any other spanning tree. This is the optimization problem Kruskal's algorithm solves.
Graph (discrete mathematics): A mathematical structure consisting of vertices and edges connecting pairs of vertices. Kruskal's algorithm operates on weighted graphs.
Prim's algorithm: A greedy algorithm that grows a minimum spanning tree from one starting vertex by repeatedly adding a cheapest connecting edge. It builds outward from a tree, unlike Kruskal's global edge ordering.
Minimum-cost network design: The problem of connecting locations or devices while minimizing the total cost of selected links. Kruskal's algorithm gives an optimal tree when links have fixed additive costs.
Disjoint-set data structure: A data structure that maintains a partition of elements and supports merging sets and testing whether elements share a set. It efficiently tests whether an edge would join vertices already connected.
Weighted graph: A graph whose edges carry numerical values representing costs, lengths, or other quantities. The edge weights determine the order in which Kruskal considers edges.
Borůvka's algorithm: A minimum-spanning-tree algorithm that repeatedly adds each component's cheapest outgoing edge. It selects edges by component rather than scanning one globally sorted list.
Single-linkage clustering: A hierarchical clustering method that joins the closest clusters according to their minimum pairwise distance. Its cluster merges correspond to edges selected by a minimum spanning tree.
Greedy algorithm: An algorithmic strategy that builds a solution through locally optimal choices. Kruskal's algorithm chooses the lightest currently eligible edge at each step.
Spanning tree: A connected, acyclic subgraph that includes every vertex of a connected graph. Kruskal's output must connect all vertices without forming cycles.

Linked from 4 pages