Skip to content
Hello Python

Select Kruskal Tree Edges

Practice ExerciseIntermediateMediumGraphKruskal

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 kruskal_edges(node_count, edges). Undirected edges are [u,v,weight]. Sort by (weight,min(u,v),max(u,v)); return selected edges as [min(u,v),max(u,v),weight], or [] if disconnected.

Starter code

def kruskal_edges(node_count, edges):
    pass
Test cases

cycle-skip

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

Expected: [[0,1,1],[2,3,1],[1,2,2]]

disconnected

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

Expected: []

Wizard outline
  1. Step 1: Handle a tree with no selected edges

    Return an empty edge list for at most one node. A trivial tree is complete before edge ordering begins.

  2. Step 2: Order an already cycle-free tree

    Normalize endpoints and return tree-shaped edges by increasing weight. Kruskal decisions begin with deterministic global edge order.

  3. Step 3: Filter edges that close a cycle

    Use root identity to accept only component-joining edges. Kruskal preserves a forest invariant after every accepted edge.

Footguns and prerequisites
  • Returning a partial forest for disconnected input hides failure.
  • Tie order must follow the documented normalized endpoints.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Normalize endpoints, sort by the documented tuple, and union distinct components.

Why it works: The cut property makes each accepted lightest cross-component edge safe, and union-find prevents cycles. Exactly V-1 accepted edges form the deterministic MST selection.

def kruskal_edges(node_count, edges):
    if node_count <= 1:
        return []
    parent = list(range(node_count))
    def find(node):
        while node != parent[node]:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
    chosen = []
    ordered = sorted(
        (weight, min(left, right), max(left, right))
        for left, right, weight in edges
    )
    for weight, left, right in ordered:
        a, b = find(left), find(right)
        if a == b:
            continue
        parent[b] = a
        chosen.append([left, right, weight])
        if len(chosen) == node_count - 1:
            break
    return chosen if len(chosen) == node_count - 1 else []