Kruskal's Spanning Tree

The Idea

A minimum spanning tree connects every node as cheaply as possible. Kruskal sorts all edges by weight and walks the list, keeping an edge only when its two ends still belong to different pieces. Union-find answers that question in near-constant time. Stop after V-1 accepted edges — the rest would only close cycles.

Real-World Example

A campus laying fibre between buildings. Trenching quotes differ wildly, so the crew digs the cheapest remaining trench, unless both of its buildings are already reachable through cable that exists. Every trench dug either joins two networks or is a waste.

The Code

edges = [(1, "a", "b"), (4, "b", "c"), (3, "a", "c"), (2, "c", "d"), (5, "b", "d")]
parent = {n: n for n in "abcd"}

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]    # path compression
        x = parent[x]
    return x

total, tree = 0, []
for w, u, v in sorted(edges):            # cheapest edge first
    ru, rv = find(u), find(v)
    if ru != rv:                         # different pieces, so no cycle
        parent[ru] = rv
        tree.append((u, v))
        total += w

print(tree, total)   # [('a', 'b'), ('c', 'd'), ('a', 'c')] 6

parent = {n: n for n in "abc"}

def find(x):
  while parent[x] != x:
      x = parent[x]
  return x

kept = 0
for w, u, v in sorted([(1, "a", "b"), (2, "b", "c"), (3, "a", "c")]):
  if find(u) != find(v):
      parent[find(u)] = find(v)
      kept += 1
print(kept)