A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted graph that connects all the vertices together with the minimum possible total edge weight. In other words, it is the cheapest or minimum cost subgraph in a given graph that connects all the nodes in the graph.
For example, for the undirected weighted graph shown below:
Below is how the minimum spanning tree looks like:
Properties of Minimum Spanning Tree (MST)
A subgraph is considered a Minimum Spanning Tree (MST) if it satisfies the following criteria:
- Connectivity: The subgraph must be a connected graph, meaning that there is a path between any two vertices in the graph. For example, the below graph is not a minimum spanning tree as there are no direct/indirect connections between nodes
A,D,Eand nodesB,C,F.
- Acyclicity: The subgraph must be acyclic, which means it does not contain any cycles. In other words, there is only one unique path between any two vertices in the subgraph. For example, the graph below is not a minimum spanning tree as there is a cycle between nodes
A,D,E.
- Minimum Total Edge Weight: The sum of the weights of all the edges in the subgraph must be the minimum possible among all the connected, acyclic subgraphs of the original graph. For example, the graph is not a minimum spanning tree, as a longer path is used even when there is an option to use much shorter path.
Taking into account all the above properties, below is a valid Minimum Spanning tree for the example graph show at the beginning:
Applications of Minimum Spanning Trees
Finding Minimum Spanning Trees (MSTs) has applications across diverse fields, including network design, logistics, transportation planning, and numerous other domains where the goal is to connect a set of points or nodes in the most efficient and cost-effective manner. By identifying the MST, organizations can minimize the total cost or distance required to link all nodes, a crucial factor in optimizing critical infrastructure such as communication networks, power grids, and transportation systems.
For example, let’s say there is a broadband company that needs to connect multiple cities using as little fiber cable as possible. The most efficient way to connect cities can be calculated by modeling cities as nodes in a graph, direct connections between each city as edges in the graph, and by computing the minimum spanning tree. This approach ensures that all cities are connected while minimizing the total length of cable required. The resulting MST would provide the optimal network layout, reducing infrastructure costs and maximizing efficiency.
Algorithms for Finding MST
The two most widely known and used algorithms for finding the Minimum Spanning Tree of a graph are Kruskal’s algorithm and Prim’s algorithm. Both of these approaches guarantee an optimal solution and have their own strengths depending on the characteristics of the input graph.
Kruskal’s algorithm takes a global approach, considering all edges of the graph sorted by weight and iteratively adding the lightest edge that doesn’t create a cycle. On the other hand, Prim’s algorithm adopts a local strategy, starting from an arbitrary vertex and progressively growing the tree by adding the lightest edge connecting the current tree to a new vertex. For dense graphs, Prim’s algorithm often performs better, while Kruskal’s algorithm may have an edge for sparse graphs. Other notable algorithms include Borůvka’s algorithm, which works well for parallel computing scenarios, and the Reverse-Delete algorithm, which takes an inverse approach by starting with all edges and removing the heaviest unnecessary ones.