Find the MST weight

Hard

Kruskal: sort edges, skip the cycles

Problem

Return the total weight of the minimum spanning tree (Kruskal's algorithm).

In simple words

Grow the tree from any node, always adding the cheapest edge that reaches a new node (min-heap).

The idea

Sort every edge by weight and add it unless its endpoints are already connected, which union-find tests instantly. Taking the cheapest safe edge each time is provably optimal, and the tree completes after V-1 edges.

The trick

Stop once V-1 edges are chosen.
Union-find is what makes the cycle test cheap.
Prim's algorithm is better on dense graphs.

←→stepspaceplay

1/10

Optimal

timeO(α(n))spaceO(n)

Almost constant per op.

1function find(x) {2  while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; }3  return x;4}5function union(a, b) {6  a = find(a); b = find(b);7  if (a === b) return false;8  if (rank[a] < rank[b]) [a, b] = [b, a];9  p[b] = a; if (rank[a] === rank[b]) rank[a]++;10  return true;11}

Input

nodes: 5, 0 edges

Memory

groups: —

Output

groups: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n=5, edges=[[0,1,2],[0,3,6],[1,2,3],[1,3,8],[1,4,5],[2,4,7],[3,4,9]]
Output:: 16
Explanation:: Cheapest tree connecting all nodes weighs 16.

Example 2

Input:: n=2, edges=[[0,1,5]]
Output:: 5
Explanation:: One edge → weight 5.

Example 3

Input:: n=3, edges=[[0,1,1],[1,2,1],[0,2,3]]
Output:: 2
Explanation:: Pick the two 1-edges → 2.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.