Minimum Spanning Tree

Visualize Kruskal's algorithm finding the minimum spanning tree of an edge-weighted graph.

Minimum Spanning Tree

Concept Overview

A Minimum Spanning Tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. In simpler terms, it's the cheapest way to connect all nodes in a network.

Mathematical Definition

Let G = (V, E) be a connected, undirected graph where V is the set of vertices and E is the set of edges. Let w: E → ℝ be a weight function that assigns a real-valued weight to each edge.

A spanning tree T is a subgraph of G such that:

T connects all vertices in V.
T is a tree (contains no cycles).
T has exactly |V| - 1 edges.

A Minimum Spanning Tree is a spanning tree T that minimizes the total weight W(T), defined as the sum of weights of all its edges:

W(T) = Σ_{e ∈ T} w(e)

Algorithms for Finding MSTs

There are several greedy algorithms designed to find the minimum spanning tree of a graph. The two most famous are Kruskal's Algorithm and Prim's Algorithm. Both are based on the cut property of minimum spanning trees.

Kruskal's Algorithm

Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree.

Sort all edges in non-decreasing order of their weight.
Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
Repeat step 2 until there are |V| - 1 edges in the spanning tree.

To efficiently check for cycles, Kruskal's algorithm typically uses a Disjoint-Set (Union-Find) data structure. The time complexity is O(E log E) or O(E log V), where E is the number of edges and V is the number of vertices.

Prim's Algorithm

Prim's algorithm operates by building the tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

Initialize a tree with a single, arbitrary vertex from the graph.
Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
Repeat step 2 (until all vertices are in the tree).

Using a Fibonacci heap, Prim's algorithm runs in O(E + V log V) time, making it faster than Kruskal's for dense graphs (where E is close to V²).

Historical Context

The Minimum Spanning Tree problem was first formulated and solved by Czech mathematician Vojt&ecaron;ch Jarník in 1930 during his work on efficient electrical network design. His algorithm was later rediscovered by Robert Prim in 1957, and is widely known as Prim's algorithm. Joseph Kruskal published his algorithm in 1956, independently of Jarník and Prim.

Real-world Applications

Network Design: Designing efficient physical networks like telecommunication networks, electrical grids, and computer networks to minimize the cost of laying cable or wire.
Clustering: In data science, constructing an MST and then dropping the longest edges is a method for single-linkage clustering, identifying clusters of closely related data points.
Approximation Algorithms: MSTs are used as a building block for solving harder problems, such as providing a 2-approximation for the metric Traveling Salesperson Problem (TSP).
Image Segmentation: Using graph-theoretic clustering approaches based on MSTs to segment images in computer vision.

Related Concepts

Dijkstra's Algorithm: Unlike MST which minimizes total tree weight, Dijkstra finds the shortest paths from a single source to all other nodes.
Greedy Algorithms: Both Kruskal's and Prim's are classic examples of greedy algorithms, where a local optimal choice leads to a global optimum.
Disjoint-Set (Union-Find): The fundamental data structure used to efficiently implement Kruskal's algorithm.

Minimum Spanning Tree