Skip to main content

Kruskal with Union-Find

What This Concept Is​

Kruskal sorts undirected edges by nondecreasing weight and adds an edge exactly when its endpoints lie in different current forest components. A disjoint-set structure supports find and union; union by size/rank with path compression gives inverse-Ackermann amortized operation bounds. Preserve original edge IDs through sorting, especially with parallel records and tied weights.

Why It Matters Here​

The data structure enforces acyclicity; the cut property establishes optimality. Neither argument replaces the other. Sorting all edges and initializing every declared vertex also matter for runtime, including empty and disconnected graphs.

Concrete Examples​

With four vertices and edges 0–1:2,1–2:-1,0–2:4, process the -1 edge first, then weight 2; skip weight 4 because it closes a cycle. Return total 1 and two original edge IDs. Vertex 3 remains an isolated one-vertex tree. A negative self-loop is still excluded because it cannot be part of a forest.

For an accepted edge, consider the cut formed by one current component. No chosen forest edge crosses it, and no lighter unprocessed crossing edge was skipped without already connecting its endpoints. The edge is safe by the respecting-cut exchange argument. Repeat until every original component is spanned.

Common Confusion / Misconceptions​

A forest on disconnected input does not require V-1 selected edges: it requires V-c. Testing only summed weight permits cycles or disconnected witnesses to slip through. Parallel edge identity must survive so the reported sum and input records can be independently verified. Union-find does not encode graph paths; its parent links are internal component bookkeeping.

How To Use It​

Price O(V+E log(E+2)) time and O(V+E) storage for the lab implementation, including sorted edge IDs and representation copies. Do not substitute log V for log E without the needed simple-graph relation. Use deterministic tie-breaking for reproducible reports while accepting all optimal witnesses in tests.

Check Yourself​

  1. What proves acyclicity and what proves minimum weight?
  2. Why does union-find's parent array not reconstruct an MST route?
  3. How many edges are needed with c components?
  4. Why preserve an edge's original identity?

Mini Drill or Application​

Implement Lab C. Independently enumerate all subsets with V-c edges on tiny graphs, retaining those with the original connectivity, and compare optimum costs. Test tied edges, parallel edges, isolated vertices, loops and negative weights. See P14.

Read This Only If Stuck​

Find Kruskal, disjoint sets, and minimum spanning forests in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.