Skip to content
Hello Python

Measure a Minimum Spanning Tree

Practice ExerciseIntermediateMediumGraphMinimum Spanning Tree

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement minimum_spanning_weight(node_count, edges). Undirected edges are [u,v,weight]. Return the MST weight, or -1 when no spanning tree exists.

Starter code

def minimum_spanning_weight(node_count, edges):
    pass
Test cases

skip-cycle

{
  "args": [
    4,
    [
      [
        0,
        1,
        1
      ],
      [
        1,
        2,
        2
      ],
      [
        0,
        2,
        5
      ],
      [
        2,
        3,
        1
      ]
    ]
  ]
}

Expected: 4

disconnected

{
  "args": [
    4,
    [
      [
        0,
        1,
        2
      ],
      [
        2,
        3,
        3
      ]
    ]
  ]
}

Expected: -1

Wizard outline
  1. Step 1: Handle a graph with no required edge

    Return zero when at most one node is already connected. A one-node tree has weight zero and needs no Union-Find state.

  2. Step 2: Measure an already tree-shaped graph

    Sum the weights when exactly node_count - 1 edges are supplied. A tree-shaped input makes the target edge count observable before cycle filtering.

  3. Step 3: Choose the lightest cycle-free edges

    Use Kruskal selection and reject disconnected graphs. Union-Find admits an edge exactly when it joins two components.

Footguns and prerequisites
  • Returning a forest weight for disconnected input is not a spanning tree.
  • Adding an edge inside one component creates a cycle.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Run Kruskal with union-find and verify that exactly V-1 edges were accepted.

Why it works: The cut property makes every lightest edge joining two current components safe. Union-find rejects cycles; V-1 accepted edges connect all vertices and therefore form an MST.

def minimum_spanning_weight(node_count, edges):
    if node_count <= 1:
        return 0
    parent = list(range(node_count))
    size = [1] * node_count
    def find(node):
        while node != parent[node]:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
    total = used = 0
    for left, right, weight in sorted(edges, key=lambda edge: edge[2]):
        a, b = find(left), find(right)
        if a == b:
            continue
        if size[a] < size[b]: a, b = b, a
        parent[b] = a; size[a] += size[b]
        total += weight; used += 1
        if used == node_count - 1: break
    return total if used == node_count - 1 else -1