Find the MST Weight

Given a weighted undirected graph with V vertices (0 .. V-1) and edges edges[i] = [u, v, w], return the total weight of its minimum spanning tree — the cheapest set of edges that connects every vertex without a cycle. If the graph is disconnected, return the total weight of the minimum spanning forest (an MST per component).

Hints

· Stuck? Reveal one nudge at a time.

An MST is the lightest set of edges connecting all vertices without a cycle.

Kruskal: sort edges and add each with union-find unless it forms a cycle.

Prim: grow a tree from a vertex, always adding the cheapest boundary edge via a min-heap.

Common doubts

The cut property: for any partition of the vertices, the lightest edge crossing it belongs to some MST, so adding it never overshoots.

Both give the same weight. Kruskal (sort + union-find) suits sparse graphs; Prim (heap) suits dense ones.

There's no single spanning tree; return the minimum spanning forest — the sum of each component's MST.

Interview follow-ups

· What an interviewer asks next.

Record each edge you add during Kruskal or Prim.

Sort edges descending (Kruskal) or use a max-heap (Prim).

Fun facts

Kruskal's cycle check is the textbook application of union-find.
Borůvka's algorithm (1926) predates both and parallelises nicely.

Asked at

AmazonGoogleMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: V = 4, edges = [[0,1,1],[1,2,2],[2,3,3],[0,3,4]]
Output: 6
Edges 1 + 2 + 3 connect all four vertices; the weight-4 edge would form a cycle.

Example 2

Input: V = 3, edges = [[0,1,5],[1,2,3],[0,2,1]]
Output: 4
Pick weights 1 and 3; skip 5.

Constraints

- 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - 1 <= w <= 10^4 - undirected edges

A minimum spanning tree is the lightest way to connect all vertices. Two greedy algorithms build it:

Prim (grow a tree). Start at a vertex and repeatedly pull the cheapest edge leaving the current tree to a new vertex, using a min-heap of candidate edges. Restart on any unvisited vertex to cover a disconnected graph. O(E log V).

Kruskal (sort edges). Sort all edges by weight and add each one unless it forms a cycle (its endpoints are already connected, checked with union-find). Each added edge joins two trees; you're done after connecting everything. O(E log E).

Both are greedy and both give the same total weight (unique when weights are distinct) — a consequence of the cut property: the lightest edge crossing any cut is safe to include.

Prerequisites

Before you start

· Concepts used directly in the solution.

Cut property. the lightest crossing edge is in some MST.

Union-Find / min-heap. the engines of Kruskal / Prim.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Just the weight, or the edges?”

The total weight.

“What if the graph is disconnected?”

Sum the MST weight of each component (a spanning forest).

The ideal opening — say it like this

I sort edges and add each with union-find unless it makes a cycle (Kruskal), or grow a tree with a min-heap of the cheapest boundary edges (Prim).

Both give the same total weight by the cut property.

Understand the problem

Worked example — V = 4, edges [[0,1,1],[1,2,2],[2,3,3],[0,3,4]]

Kruskal: add 1 (0-1), 2 (1-2), 3 (2-3); skip 4 (would cycle)
total = 6

Key observations

1Aha

Greedy is optimal (cut property)

The lightest crossing edge is always safe.

2Aha

Kruskal uses union-find to skip cycles

Add an edge only if it joins two different sets.

3Aha

Same weight either way

Prim and Kruskal agree on the total.

Brute force vs optimal

	Prim (heap)	Kruskal (union-find)
Idea	grow a tree by cheapest boundary edge	sort edges, add if no cycle
Time	O(E log V)	O(E log E)
Best for	dense graphs	sparse graphs

Both compute the same minimum total weight. Full code is in the Approaches selector below.

Summary

Key takeaway

An MST is the lightest cycle-free connector. Kruskal: sort edges, add with union-find unless a cycle. Prim: grow a tree via a min-heap of boundary edges. Both give the same total weight.

kruskal: sort edges; for each (u,v,w): if find(u)!=find(v): union, total += w