DAA Greedy MST 26

MST (Kruskal’s Algorithm)

Greedy rule: process edges in nondecreasing weight and accept an edge only if it connects two different DSU sets (otherwise it forms a cycle).

← Index ↗ Union-Find (25)

Graph (Plotly)

Speed
Preset Show weights Show DSU set id
MST edges
0
Total weight
0
Current edge
—
Sorted edges (ascending weight)
—
Pseudocode (Kruskal)
Line: —

Step Explanation

Click Start to load graph, sort edges, initialize DSU. Then press Step.

Notes: why it works + complexity
  • Greedy rule: try the next lightest edge.
  • Cycle check: accept (u,v) iff DSU representatives differ.
  • Cut property: the lightest edge crossing any cut is safe for MST.
  • Time: sorting dominates ⇒ O(E log E); DSU ops ~ constant amortized.

Course designed by Abhay Singh Bisht. Connect on LinkedIn →