Prim's Minimum Spanning Tree

Implement Prim's algorithm to find the total weight of a minimum spanning tree.

graphs mst prim heap

Write a function `mst_weight(n, edges)` that takes an integer `n` (number of vertices, labeled 0 to n-1) and a list of edges, where each edge is a tuple `(u, v, w)` representing an undirected edge between vertices `u` and `v` with weight `w`. The graph is connected and has no self-loops. Return the total weight of a minimum spanning tree (MST) of the graph. Your solution should implement Prim's algorithm. You may use any standard library. The function signature is exactly `mst_weight(n, edges)`.

Constraints

2 <= n <= 1000, number of edges up to 10^4, edge weights are positive integers <= 10^4. The graph is connected.

Example

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

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a priority queue to always pick the smallest edge connecting the current tree to a new vertex.

Keep a visited set to track vertices already in the MST.

Initialize with vertex 0 and add its edges to the heap.

When you pop an edge, if the target is unvisited, include its weight and add that vertex's edges.

Test Results

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