How it works?

Keep a boolean inTree for each vertex. Start with only vertex 0 in the tree. The frontier is every edge with exactly one endpoint inside the tree, called a crossing edge.

Step-by-Step Process:

1. Among all crossing edges, pick the one with the smallest weight.
2. Add its outside endpoint to the tree and add its weight to the total.
3. Repeat until the tree contains all n vertices (that takes n - 1 edges).

If at some point no crossing edge exists but vertices remain outside, the graph is disconnected.

Example with edges [0,1,1, 1,2,2, 2,3,3, 0,3,4]: from 0 take 0-1(1), then 1-2(2), then 2-3(3); total 6.