Skip to content
Hello Python
Algorithm1 Practice2 Interview

Kruskal

Build a minimum spanning tree by taking sorted edges that join different components. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Kruskal when the prompt's constraints and required operations match this shape: Build a minimum spanning tree by taking sorted edges that join different components.

Pybit demonstrates Kruskal in a professional Python interview workspace.
On this page · Process Edges by Increasing Weight

Checking your account…

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

Kruskal Code Labs

Process Edges by Increasing Weight

Kruskal considers undirected edges globally from lightest to heaviest. Accepted edges form a forest that gradually joins components.

Add Only Edges Joining Components

An edge whose endpoints have different roots connects two trees and is safe by the cut property. Equal roots mean the edge closes a cycle and must be rejected.

Trace Kruskal Edge Decisions

Reference
def kruskal_trace(node_count,edges):
    parent=list(range(node_count));trace=[]
    def find(node):
        if parent[node]!=node:parent[node]=find(parent[node])
        return parent[node]
    for edge in sorted(edges):
        weight,left,right=edge;a,b=find(left),find(right);accepted=a!=b
        if accepted:parent[b]=a
        trace.append([edge.copy(),accepted])
    return trace
Practice

Implement kruskal_trace(node_count,edges). Edges are [weight,u,v]; return [edge,accepted] in sorted order.

Public tests

  • Reject edges within one component

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Use Union Find for Cycle Prevention

Union-find supplies near-constant amortized component checks. Path compression and union by size keep its forest shallow while accepted-edge count tracks completion.

Compute Kruskal MST Weight

Reference
def kruskal_weight(node_count,edges):
    parent=list(range(node_count));size=[1]*node_count;total=used=0
    def find(node):
        if parent[node]!=node:parent[node]=find(parent[node])
        return parent[node]
    for weight,left,right in sorted(edges):
        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
    return total if used==node_count-1 else None
Practice

Implement kruskal_weight(node_count,edges). Return MST weight or None when disconnected.

Public tests

  • Stop after connecting all components

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Kruskal or Prim

Choose Kruskal for sparse edge lists, pre-sorted edges, or minimum spanning forests. Choose Prim when an adjacency representation and one connected growth frontier are more convenient. Sorting makes Kruskal O(E log E).

Explain It in an Interview

Say: “The next lightest edge crossing two current components is safe; union-find rejects cycle edges.” Stop after V minus one accepted edges and report failure or a forest when components remain.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Kruskal complete workflowO(E log E)O(E log E)Normalize endpoints, sort by the documented tuple, and union distinct components.

Space

O(V + E) for the focused Select Kruskal Tree Edges implementation.

Assumptions

  • 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.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Kruskal invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The selected edges remain acyclic.
  3. Each accepted edge reduces the number of disconnected tree components by one.
  4. Normalize and sort edges deterministically. Preserve this claim after every transition.
  5. Use union-find to accept only cross-component edges. Preserve this claim after every transition.

When To Use Or Avoid Kruskal

Use It When

  • Use Kruskal when this precondition is stated or can be proved: The weighted graph is undirected, and the required output connects each component without cycles.
  • Use it when this maintained state removes repeated work: The selected edges remain acyclic.

Choose Another Tool When

  • Avoid Kruskal when this precondition is absent: The weighted graph is undirected, and the required output connects each component without cycles.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The weighted graph is undirected, and the required output connects each component without cycles.

Avoid

def kruskal_edges(node_count, edges):
    pass

Use instead

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 = []
    for weight, left, right in sorted((weight, min(left,right), max(left,right)) for left,right,weight in edges):
        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 []

Where you will hit this: Select Kruskal Tree Edges(opens in a new tab)

Breaking the state transition

Returns the first V-1 edges and includes a cycle.

Prevent it: Preserve this proof obligation: The cut property makes each chosen minimum crossing edge compatible with some minimum spanning tree.

Avoid

def kruskal_edges(n,edges):
    return [[min(u,v),max(u,v),w] for u,v,w in edges[:n-1]]

Use instead

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 = []
    for weight, left, right in sorted((weight, min(left,right), max(left,right)) for left,right,weight in edges):
        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 []

Where you will hit this: Select Kruskal Tree Edges(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(E log E).

Avoid

def kruskal_edges(n,edges):
    return [[min(u,v),max(u,v),w] for u,v,w in edges[:n-1]]

Use instead

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 = []
    for weight, left, right in sorted((weight, min(left,right), max(left,right)) for left,right,weight in edges):
        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 []

Where you will hit this: Maximum Container Area(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.