Kruskal MST

Find the minimum spanning tree weight using Kruskal's algorithm.

graphs minimum-spanning-tree union-find kruskal

Given a connected undirected graph with `n` nodes (numbered 0 to n-1) and a list of edges, each edge is a tuple `(u, v, w)` where `u` and `v` are the endpoints and `w` is the edge weight. Your task is to implement the function `kruskal_mst(n, edges)` that returns the total weight of the minimum spanning tree (MST). The graph is guaranteed to be connected, so an MST exists.

Implement Kruskal's algorithm: sort edges by weight, add an edge if it connects two different components (using a union-find structure), and stop when you have added n-1 edges. Sum the weights of the added edges.

Constraints

1 <= n <= 10^4
0 <= len(edges) <= 10^5 (graph is connected, so at least n-1 edges)
Edges are 0-indexed. Edge weights can be any integer (possibly negative, but no overflow concerns in Python).
Time complexity must be O(E log E) due to sorting.

Example

>>> kruskal_mst(3, [(0,1,5), (1,2,3), (0,2,1)])
4
>>> kruskal_mst(4, [(0,1,10), (0,2,6), (0,3,5), (1,3,15), (2,3,4)])
19
>>> kruskal_mst(2, [(0,1,7)])
7

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sort the edges by weight ascending.

Use union-find (disjoint set) with path compression and union by rank to track components.

Iterate sorted edges and add the edge if its endpoints are in different components; stop after n-1 edges.

Sum the weights of the added edges.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.