Minimum Spanning Trees (MST)

Minimum Spanning Tree (MST) is a fundamental concept in graph theory and algorithms. Given a connected, weighted graph, an MST is a spanning tree (a subset of the edges that keeps the graph connected without any cycles) that has the minimum possible total edge weight. In other words, the MST connects all vertices together with the smallest total cost. For example, if vertices represent cities and edge weights represent the cost of building roads between them, an MST would be the set of roads connecting all cities at the lowest total cost.

Key Properties of MSTs

Real-World Applications of MST

MSTs have many practical applications where a set of points needs to be connected with minimal cost:

Kruskal’s Algorithm – Greedy Edge Selection

Kruskal’s algorithm builds an MST by iteratively adding the next smallest edge that doesn’t form a cycle. It treats the graph as a forest (collection of trees) and merges the trees together with lightest edges until a single tree spans all vertices. The algorithm steps are:

This algorithm uses the Union-Find (Disjoint Set Union) data structure to efficiently check for cycles. Union-Find keeps track of which vertices are in the same connected component. When an edge connects two vertices that are already in the same component, it would form a cycle and is therefore skipped.

Below is pseudocode for Kruskal’s algorithm:

// Kruskal's MST Algorithm
Kruskal(G):
    MST = ∅
    for each vertex v in G:
        MakeSet(v)              // initialize disjoint sets
    sort edges of G by weight (in increasing order)
    for each edge (u,v) in sorted order:
        if FindSet(u) ≠ FindSet(v):   // if u and v are in different components
            MST = Union(MST, {(u,v)})       // add edge to MST
            Union(u, v)              // merge the components
    return MST

During the iteration, if an edge is rejected (because FindSet(u) == FindSet(v), meaning there’s already a path between those vertices), the algorithm moves on to the next edge. Kruskal’s algorithm has a time complexity of about O(E log E) (dominated by sorting the edges), which is effectively O(E log V) for a graph with V vertices and E edges. Using Union-Find with path compression and union by rank, each union or find operation is almost constant time on average.

Prim’s Algorithm – Greedy Tree Growth

Prim’s algorithm builds the MST by starting from an arbitrary vertex and growing the tree one edge at a time. It maintains a set of vertices already in the MST and at each step adds the smallest weight edge that connects a vertex in the MST to a vertex outside the MST. The steps are:

Prim’s algorithm can be efficiently implemented using a min-heap (priority queue) to always pick the next smallest edge. It typically runs in O(E log V) time as well (or O(V2) without a min-heap, if using a simple array to find the minimum edge each time). The pseudocode for Prim’s algorithm is given below:

// Prim's MST Algorithm (assuming graph G with vertices V)
Prim(G):
    MST = ∅
    let U = { arbitrary start vertex }
    while (U ≠ V):
        // find the minimum weight edge (u, v) with u ∈ U and v ∉ U
        find (u, v) with minimum weight such that u ∈ U and v ∉ U
        MST = Union(MST, {(u, v)})
        U = Union(U ∪ {v})
    return MST

In practice, Prim’s algorithm starts from an initial vertex and uses a priority queue to track the cheapest edge leading out from the current tree. Each time a new vertex v is added to the MST, the edges from v to its neighbors are examined to update the candidate edges. Unselected edges that would form a cycle (connecting to a vertex already in U) are ignored implicitly, because the algorithm always picks an edge connecting to a new vertex. Prim’s and Kruskal’s algorithms will both yield an MST when applied correctly, but they build the tree in different ways – Prim’s grows one connected component, whereas Kruskal’s can connect components in any order.

Algorithm Comparison

Algorithm Approach Data Structures Time Complexity When to Use
Kruskal’s Greedy by edge weight (global minimum edges first) Union-Find for cycle detection; sorting of edges O(E log V) (due to sorting edges) Good for sparse graphs; easy to implement if edges are readily available
Prim’s Greedy by growing a tree (local minimum edge from current tree) Priority queue (min-heap) for selecting next edge; adjacency list O(E log V) (with min-heap) or O(V2) without heap Often chosen for dense graphs or when adjacency list is available for efficiency

Interactive MST Visualization

Below, you can interactively visualize how Kruskal’s and Prim’s algorithms construct an MST. Select an algorithm, then click "Start" to initialize. Use "Next Step" to advance the algorithm step by step. The graph’s vertices (A–F) are connected by weighted edges. As you step through, edges chosen for the MST will be highlighted in green, and you’ll see which edges are added or skipped at each step.

Algorithm:

Select an algorithm and click Start to begin.

A B C D E F 2 2 3 4 5 5 6 7

Programming Exercises

To reinforce the concepts, try the following programming exercises in C++. You may use the Graph.h class for your implementation.

  1. Implement Kruskal’s MST: Write a C++ program that reads a graph’s edges and outputs its minimum spanning tree using Kruskal’s algorithm. You will need to:

    Test your implementation on a small graph (you can use the example graph from the visualization above) to ensure it picks the correct edges.

    Answer: here

  2. Implement Prim’s MST: Write a C++ program to compute an MST using Prim’s algorithm. Hints:

    Ensure your program outputs the total weight of the MST and the list of edges chosen.

    Answer: here

    Google doc