Skip to main content

Write Kruskal's algorithm

Short answer

Kruskal's algorithm: initialize each vertex as a separate set, sort edges by weight, and for each edge in order, if its endpoints are in different sets, add it to the MST and union the sets. Time O(E log E).

Write Kruskal's algorithm for minimum spanning tree.

KRUSKAL(G)                       // G = (V, E) connected, weighted, undirected
1. T = empty
2. for each vertex v: MAKE-SET(v)
3. sort E in non-decreasing order of weight
4. for each edge (u, v) in sorted order
5.     if FIND-SET(u) != FIND-SET(v)      // no cycle is formed
6.         T = T + {(u, v)}
7.         UNION(u, v)
8. return T                      // MST with V-1 edges

Time complexity: O(E log E), dominated by sorting.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 10 questions →