Algorithms and data structures · Intermediate

Kruskal’s algorithm: take light edges without forming cycles

Sort weighted edges and use disjoint sets to distinguish useful component joins from cycle-forming edges.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. A spanning tree is not a shortest-path tree
  2. Follow sorted edge decisions
  3. Use disjoint sets for cycle decisions
  4. Handle ties and disconnected input
  5. Ask Logeia about this articleCheck your understanding

A spanning tree is not a shortest-path tree

Kruskal’s algorithm finds a minimum-weight spanning tree in an undirected weighted graph. It minimizes the sum of selected edge weights while connecting all vertices without cycles. That objective differs from minimizing distances from one source. A disconnected graph instead yields a minimum spanning forest, one tree per connected component. Negative edge weights are permitted. They do not justify adding extra cycle edges, because the output must remain a tree or forest. In a connected graph, a spanning tree on V vertices has exactly V−1 selected edges.

Follow sorted edge decisions

Take edges A−B of weight 1, B−C of weight 2, A−C of weight 3, C−D of weight 4 and B−D of weight 5. Select A−B and B−C. Skip A−C because its endpoints are already connected in the selected forest. Then select C−D, connecting all four vertices with total weight 7. The selected structure need not be connected at intermediate stages. It can consist of several separate trees that are joined by later edges. Each accepted edge reduces the number of components by one without creating a cycle.

Use disjoint sets for cycle decisions

A disjoint-set structure stores a representative for each current component. If find(u) differs from find(v), edge u−v can be accepted and the sets merged. If the representatives agree, the selected forest already contains a path between the endpoints, so adding the edge would create a cycle. Path compression and union by size improve the bookkeeping cost. They do not themselves decide which weights are optimal. Keep the roles separate: sorted greedy consideration identifies light candidates, while disjoint sets determine whether a candidate safely joins different components.

Handle ties and disconnected input

Ordinary edge sorting costs O(E log E), which dominates an efficient disjoint-set implementation’s operations. Already sorted edges can be analyzed separately. Equal edge weights may allow several different minimum spanning trees; differing selected edge sets are not automatically errors. Self-loops are never accepted, and parallel edges can be processed as distinct candidates. If the input is disconnected, failing to collect V−1 edges should not be disguised as success at constructing a spanning tree. Specify whether the interface returns the valid minimum spanning forest or reports the absence of a single spanning tree.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 11

Choose a learning path