Types of Graphs > Minimum Spanning Tree
What is a Minimum Spanning Tree?
A minimum spanning tree is a special kind of tree that minimizes the lengths (or “weights”) of the edges of the tree. An example is a cable company wanting to lay line to multiple neighborhoods; by minimizing the amount of cable laid, the cable company will save money.
A tree has one path joins any two vertices. A spanning tree of a graph is a tree that:
- Contains all the original graph’s vertices.
- Reaches out to (spans) all vertices.
- Is acyclic. In other words, the graph doesn’t have any nodes which loop back to itself.
As you can probably imagine, larger graphs have more nodes and many more possibilities for subgraphs. The number of subgraphs can quickly reach into the millions, or billions, making it very difficult (and sometimes impossible) to find the minimum spanning tree. Additionally, the lengths usually have different weights; one 5m long edge might be given a weight of 5, another of the same length might be given a weight of 7.
A few popular algorithms for finding this minimum distance include: Kruskal’s algorithm, Prim’s algorithm and Boruvka’s algorithm. These work for simple spanning trees. For more complex graphs, you’ll probably need to use software.
Kruskal’s algorithm example
Find the edge with the least weight and highlight it. For this example graph, I’ve highlighted the top edge (from A to C) in red. It has the lowest weight (of 1):
Find the next edge with the lowest weight and highlight it:
Continue selecting the lowest edges until all nodes are in the same tree.
- If you have more than one edge with the same weight, choose an edge with the lowest weight.
- Be careful not to complete a cycle (route one node back to itself). If your choice completes a cycle, discard your choice and move onto the next largest weight.
Real Life Applications
Minimum spanning trees are used for network designs (i.e. telephone or cable networks). They are also used to find approximate solutions for complex mathematical problems like the Traveling Salesman Problem. Other, diverse applications include:
- Cluster Analysis.
- Real-time face tracking and verification (i.e. locating human faces in a video stream).
- Protocols in computer science to avoid network cycles.
- Entropy based image registration.
- Max bottleneck paths.
- Dithering (adding white noise to a digital recording in order to reduce distortion).