Minimum Spanning Tree (Kruskal's & Prim's)

Given a weighted, **undirected**, connected graph with **n** vertices, find the total weight of its **Minimum Spanning Tree (MST)** — the subset of edges that connects all vertices with the minimum possible total edge weight and no cycles.

Implement this using **Kruskal's algorithm** (sort edges + Union-Find).

Examples

Input: n = 4, edges = [[0,1,1],[1,2,2],[2,3,3],[0,3,4],[0,2,5]]

Output: 6

MST uses edges (0,1,1), (1,2,2), (2,3,3) for total weight 6.

Input: n = 2, edges = [[0,1,7]]

Output: 7

Only one possible edge.

Constraints

• 2 <= n <= 2000
• The graph is connected
• edges[i] = [u, v, weight]

Complexity Analysis

Time

O(E log E) for sorting edges, plus near O(E) for Union-Find with path compression.

Space

O(V) for the Union-Find parent/rank arrays.

Test Cases

#1 — Classic MST example

Input: n=4 edges=[[0,1,1],[1,2,2],[2,3,3],[0,3,4],[0,2,5]]

Expected: 6

#2 — Single edge

Input: n=2 edges=[[0,1,7]]

Expected: 7

#3 — Triangle, all equal weights

Input: n=3 edges=[[0,1,1],[1,2,1],[0,2,1]]

Expected: 2

Interactive graph explorer available!

Switch to the Visualize tab to build a custom graph and animate BFS traversal to test your intuition.