Minimum Spanning Tree

5 min read#networks#algorithms#weighted

The cheapest set of edges that connects every node of a weighted graph without forming a loop.

Contents

Minimum Spanning Tree

Suppose you must wire up every house in a town — lay cable, build roads, run pipes — and each possible link has a cost. You want everything connected, and you want to spend as little as possible. The answer is a minimum spanning tree (MST): a subset of edges of a connected, weighted Graph that touches every node, contains no cycle, and has the smallest possible total weight.

It is a tree because connecting n nodes without any redundant loop takes exactly n-1 edges — any more would create a cycle (waste), any fewer would leave something stranded. Among all the spanning trees a graph admits, the MST is the cheapest.

Two greedy algorithms

Remarkably, you can build the optimal tree by always grabbing the cheapest edge that does not ruin the structure. Two classic algorithms formalize this:

  • Kruskal's algorithm sorts all edges by weight and adds them cheapest-first, skipping any edge that would close a cycle. It grows a forest of fragments that gradually merge into one tree. (Detecting "would this make a cycle?" efficiently is what the union–find data structure is for.)
  • Prim's algorithm grows a single tree from a starting node, repeatedly adding the cheapest edge that links the tree to a node not yet in it. This is strikingly close to Dijkstra's Algorithm — same priority-queue frontier — but Prim ranks frontier edges by their own weight, while Dijkstra ranks nodes by total distance from the source.

MST is not shortest paths

It is tempting to confuse the two weighted classics, but they optimize different things. Dijkstra's Algorithm minimizes the distance from one source to each node individually. An MST minimizes the total edge weight needed to hold the whole network together — and the path between two nodes within the MST is generally not their shortest path in the original graph. One answers "how do I get there fastest?"; the other answers "how do I connect everyone cheapest?"

Watch Prim grow the tree

Below, scattered points are cities and the cost of a link is the straight-line distance between them. Prim's algorithm starts from one city and, frame by frame, reaches out along the cheapest edge to a city not yet connected (the bright candidate). The tree that results is the least-total-length way to wire them all together.

Prim's algorithm building a minimum spanning tree over random cities. The orange edge is the cheapest link from the tree to an unconnected city, about to be locked in. Re-runs on a fresh scatter when complete.

See also

Related topics

  • GraphA set of nodes joined by edges — the minimal mathematical object for describing relationships of any kind.
  • Dijkstra's AlgorithmFind the cheapest route in a weighted graph by greedily settling the nearest unfinished node, one at a time.
  • Breadth-First SearchExplore a graph in concentric layers from a source — the simplest way to find shortest paths in an unweighted graph.
  • Depth-First SearchPlunge as deep as possible along each branch, then backtrack — the traversal behind spanning trees, cycle detection, and topological order.
  • Graph Theory & NetworksNodes joined by edges are the universal skeleton of connection — friendships, roads, neurons, and the web all reduce to the same simple picture.
  • PageRankA node's importance is the long-run chance a random surfer following links lands on it — the dominant eigenvector of the link matrix.

Referenced by