Minimum Spanning Trees

Minimum spanning trees (MST)

A minimum spanning tree is a minimally connected subgraph of a connected, undirected weighted graph. It includes every vertex and minimizes the sum of edge weights.

It must satisfy three conditions:

1. Tree: no cycle, with $|V|-1$ edges for $|V|$ vertices.

2. Spanning: contains every original vertex and uses only original edges. Adding any original non-tree edge creates a cycle.

3. Minimum total weight.

A spanning tree exists if and only if the undirected graph is connected.

For example, the chosen edges connect all vertices with minimum total weight.

An MST need not be unique; one graph can have several MSTs.

A practical example is constructing railway connections between cities with a limited budget. Every pair need not be linked directly: an MST connects all cities at minimum total cost.

Prim

Prim's algorithm grows from a starting vertex. At each stage choose the minimum-weight edge reaching an outside vertex and add that vertex to the reached set. It finishes when all vertices are reached. This is a greedy algorithm.

Think of a small tree growing outward along its cheapest available branch.

For example:

Kruskal

Prim is organized around vertices; Kruskal is organized around edges.

Kruskal merges a forest into a tree. Process edges in increasing weight order, accepting an edge only when its endpoints are in different connected components.

For example: