In a connected weighted undirected graph a spanning tree is a set of edges that connects all vertices and has no cycles. The spanning tree of the smallest weight is the minimum spanning tree (MST). A classic example: connect offices with as little cable as possible.

A weighted graph and its MST (green edges, weight 39)
A weighted graph and its MST (green edges, weight 39)

Properties

  • An MST has exactly V - 1 edges: fewer breaks connectivity, more creates a cycle.
  • The cut property: if we split the vertices into two parts, the lightest edge between them belongs to some MST. The correctness of greedy algorithms rests on it.
  • With distinct weights the MST is unique.

Kruskal's algorithm

Sort the edges by increasing weight. Take an edge if its ends are in different components; otherwise a cycle would appear. We track the components with Union-Find. Once V - 1 edges are collected we can stop.

python
NODES = "ABCDEFG"
EDGES = [(7, "A", "B"), (5, "A", "D"), (8, "B", "C"), (9, "B", "D"), (7, "B", "E"),
         (5, "C", "E"), (15, "D", "E"), (6, "D", "F"), (8, "E", "F"), (9, "E", "G"),
         (11, "F", "G")]          # (weight, u, v): cable lengths between offices

def kruskal(nodes, edges):
    parent = {v: v for v in nodes}

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