Kruskal's Algorithm
Builds a minimum spanning tree by sorting edges by weight and adding each edge that does not create a cycle.
Optimal:YesWeighted:YesDirected:NoNegative weights:Yes
Complexity
Best
O(E log E)
Average
O(E log E)
Worst
O(E log E)
Space
O(V)
When to use: When you need a minimum spanning tree of a connected, weighted, undirected graph.Very clean with DSU (Union-Find)Requires sorting all edges
Pseudocode
make-set(v) for each v; MST = ∅sort edges by nondecreasing weightfor each edge (u,v) in sorted order:if find(u) ≠ find(v):union(u,v); add (u,v) to MSTreturn MST
Waiting to start…