Kruskal's algorithm constructs a minimum spanning tree by considering edges from lightest to heaviest.

Start with every vertex in a separate component. For each edge in sorted order:

• add it if its endpoints are in different components;
• skip it if adding it would create a cycle.

Whenever an edge is accepted, merge the two components.

The greedy choice is safe because a lightest edge connecting two current components satisfies the cut property.

Disjoint-set union supports the component tests and merges efficiently. Sorting the edges usually dominates the running time, giving a common bound of

$$O(|E|\log |E|).$$

Kruskal is especially natural when the graph is represented primarily as a collection of weighted edges.