Skip to content

Kruskal's Algorithm

Summarized notes on Introduction to Algorithms, Chapter 23

  • choose the least-weight edge that connecting distinct components \(C_1\) and \(C_2\)
  • implement using disjoint sets where each set represents a tree
    • when vertices \(u\) and \(v\) have different representative they belong to different sets
    • edge \((u, v)\) is safe to add to \(A\)
  • optimal time when using union by rank and path compression

Example

img img

Complexity

Running time
\(O(V)\) initialize sets -- \(O(1)\) \(V\) times
\(O(E \lg V)\) sort sets
\(O(E \alpha(V))\) set operations to find and union
\(O(E \lg V)\) = Kruskal's algorithm