Minimum Spanning Tree

  • Describe why constructing minimum spanning trees is useful.

When finding spanning trees of a graph, we may be interested in those where the total edge weight is minimal among all the possible spanning trees, a so-called minimum weight spanning tree (MST).

A minimum spanning tree of a weighted graph $G$ is a spanning tree of it with the minimum possible total edge weight.

Consider the following weighted graph:

Every tree below is a minimum spanning tree of the graph above.

As can be seen, an MST is not necessarily unique. There may be several minimum spanning trees of the same total weight. However, if each edge has a distinct weight, there will be only one unique minimum spanning tree.

Minimum Spanning Tree Problem

Given a connected, undirected weighted graph $G = (V, E, w)$, the minimum (weight) spanning tree problem requires finding a spanning tree of minimum weight, where the weight of a tree $T$ is defined as the sum of the wight of all its edges:

$$ w(T) = \sum_{e \in E(T)} w(e) $$

We will look at two algorithms to solve the MST problem:

  • Prim's Algorithm
  • Kruskal's Algorithm
Resources