Minimum Spanning Tree Algorithms Overview

Minimum Spanning Tree (MST) is a classic problem in graph theory. It has many real-world applications, such as designing the lowest-cost communication networks, circuit wiring, and pipeline layout.

Since implementing MST algorithms needs some other algorithms as a foundation, and this article is in the basics section, we will not explain the algorithm code in detail here.

This article mainly introduces the definition and application scenarios of minimum spanning trees, and explains the core ideas of two classic MST algorithms. The detailed code will be provided in the data structure design section.

What is a Spanning Tree

First, let's understand what a spanning tree is. Given an undirected connected graph $G$, a spanning tree is a subgraph of $G$ that includes all the vertices of $G$ and is a tree (which means it is connected and has no cycles).

In other words, a spanning tree has these features:

• It includes all the vertices from the original graph.
• The number of edges is one less than the number of vertices (V-1 edges).
• It is connected and has no cycles.

A graph can have many different spanning trees. For example, here is a weighted graph:

Here are some spanning trees. The edges in the spanning tree are marked in red:

Here is another spanning tree:

What is a Minimum Spanning Tree

If the graph is a weighted graph, the minimum spanning tree is the spanning tree with the smallest total edge weight.

For example, in the case above, the second spanning tree is the minimum spanning tree. The total weight is 2 + 3 + 5 = 10. There is no other spanning tree with a smaller total weight.

Minimum spanning trees have many real-world uses. The edge weights can represent distance, cost, time, and so on.

For example, if you want to build roads between several cities, the nodes in the graph are cities, the edges are roads, and the weights are the cost to build each road. We want to connect all the cities with the lowest total cost. This is a classic minimum spanning tree problem.

Minimum Spanning Tree Algorithms

There are two classic algorithms to solve the minimum spanning tree problem: Kruskal's algorithm and Prim's algorithm. Both use a greedy approach, but their implementation is different.

Kruskal's algorithm is simpler. First, sort all the edges in the graph by weight, then use the Union-Find algorithm to build the minimum spanning tree.

Prim's algorithm is an extension of the Dijkstra algorithm. It uses a priority queue to build the minimum spanning tree step by step.

You can find the code for these algorithms in Kruskal's Algorithm and Prim's Algorithm.