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

• Spanning tree characteristics: If a graph has n vertices, any spanning tree connects all vertices with exactly n-1 edges. A spanning tree contains no cycles; removing any edge from it will disconnect the graph.
• Minimum weight: The total weight of an MST is less than or equal to the weight of any other spanning tree of the graph. By definition, MST is optimal in terms of edge weight sum.

Real-World Applications of MST

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

• Network design: Designing minimum-cost communication, computer, or road networks. For example, MST can model laying out cables or fibers to connect multiple hubs at minimum cost (water supply networks, telecommunication networks, etc.).
• Electrical grids: Connecting nodes in an electrical grid or pipeline with minimum wiring/piping while ensuring connectivity.
• Approximation algorithms: MSTs are used in algorithms as a subroutine or baseline, for example in approximating the Traveling Salesman Problem (an MST gives a lower bound and a basis for the approximation).

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:

• Sort all edges of the graph in increasing order of weight.
• Initialize the MST as empty. Iterate through the sorted edges, and for each edge, check if adding it to the MST would create a cycle.
• If an edge can be added without creating a cycle, include it in the MST; otherwise, skip it.
• Continue until the MST has n-1 edges (where n is the number of vertices).

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:

• Start with any one vertex (initial MST has just one vertex, no edges).
• Find the lowest-weight edge between a vertex in the MST and a vertex outside the MST; add that edge (and the new vertex) to the MST.
• Repeat: at each step, among all edges that have one endpoint in the MST and the other endpoint outside, choose the minimum-weight edge and add it to the MST.
• Stop when all vertices have been included (when the MST has n-1 edges).

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

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.

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:
   • Create a Graph<V, E> and get the edges.
   • Sort the edges by weight.
   • Use a Union-Find (disjoint set) structure to check for cycles as you iterate through sorted edges.
   • Print the edges of the MST and the total weight. For instance, given an input list of edges, the program should output the MST edges (u–v pairs) and the sum of their weights.

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

   #include <iostream> #include <vector> #include <algorithm> #include <map> #include "Graph.h" template<typename V, typename E> class UnionFind { private: // For each vertex, store its parent and rank/size std::map<typename Graph<V,E>::Vertex, typename Graph<V,E>::Vertex> parent; std::map<typename Graph<V,E>::Vertex, int> rank; public: // Make each vertex a separate set void make_set(const std::list<typename Graph<V,E>::Vertex>& vertices) { // TODO: Initialize parent[v] = v, rank[v] = 0 for each v } typename Graph<V,E>::Vertex find_set(typename Graph<V,E>::Vertex v) { // TODO: If parent[v] != v, recursively set parent[v] = find_set(parent[v]) // Return the representative (root) return; } // Union by rank void union_set(typename Graph<V,E>::Vertex a, typename Graph<V,E>::Vertex b) { // TODO: union the sets containing a and b, adjusting parent and rank } }; template<typename V, typename E> void kruskal_mst(Graph<V,E>& g) { // 1. Collect edges in a std::vector std::list<typename Graph<V,E>::Edge> edgeList = g.edges(); std::vector<typename Graph<V,E>::Edge> edges(edgeList.begin(), edgeList.end()); // 2. Sort edges by weight // Hint: use e.weight() to get the weight // TODO: Implement sorting (std::sort with a custom comparator) UnionFind<V,E> uf; std::list<typename Graph<V,E>::Vertex> verts = g.vertices(); uf.make_set(verts); // 3. Kruskal iteration int mstWeight = 0; std::vector<typename Graph<V,E>::Edge> mstEdges; // TODO: Iterate over the sorted edges: // a) find each edge's endpoints // b) check if they're in the same set (cycle check) // c) if different, union them, add to MST, accumulate weight std::cout << "Kruskal MST edges:\n"; for (auto& e : mstEdges) { auto [u, v] = g.endpoints(e); std::cout << *u << " -- " << *v << " (w=" << e.weight() << ")\n"; } std::cout << "Total MST Weight = " << mstWeight << std::endl; } int main() { Graph<std::string, std::string> g(false); auto A = g.insert_vertex("A"); auto B = g.insert_vertex("B"); auto C = g.insert_vertex("C"); auto D = g.insert_vertex("D"); g.insert_edge(A, B, 1); g.insert_edge(A, C, 4); g.insert_edge(B, C, 2); g.insert_edge(B, D, 5); g.insert_edge(C, D, 3); kruskal_mst(g); return 0; } Submit

   Answer: here

2. Implement Prim’s MST: Write a C++ program to compute an MST using Prim’s algorithm. Hints:
   • Pick any start vertex (say the first one from g.vertices())
   • Use std::priority_queue to always pick the next smallest edge. You can store entries of the form (weight, vertex) in the priority queue representing the best edge to each candidate vertex.
   • Maintain an array to mark visited vertices. Initialize the queue with all edges from an arbitrary start vertex.
   • At each step, extract the minimum weight edge that leads to an unvisited vertex, add that edge to the MST, and then update the queue with edges from the new vertex.

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

   #include <iostream> #include <queue> #include <vector> #include <map> #include "Graph.h" template<typename V, typename E> void prim_mst(Graph<V,E>& g) { // If graph is empty, just return if (g.num_vertices() == 0) return; // 1. Grab the vertices, choose a start vertex auto verts = g.vertices(); auto start = verts.front(); // e.g., first vertex in the list // 2. Maintain a "visited" map to track which vertices are included in MST std::map<typename Graph<V,E>::Vertex, bool> visited; for (auto& v : verts) { visited[v] = false; } visited[start] = true; // start is initially visited // 3. Priority queue of edges, storing (weight, fromVertex, toVertex) // so we can always pick the smallest edge that leads to an unvisited vertex. using PQItem = std::tuple<int, typename Graph<V,E>::Vertex, typename Graph<V,E>::Vertex>; auto cmp = [](const PQItem& a, const PQItem& b) { // Compare by weight return std::get<0>(a) > std::get<0>(b); }; std::priority_queue<PQItem, std::vector<PQItem>, decltype(cmp)> pq(cmp); // 4. Push edges from the start vertex into pq // Hint: use g.incident_edges(start) to get all edges emanating from 'start' // TODO: for each edge e in incident_edges(start), figure out the neighboring vertex // and push {e.weight(), start, neighbor} into pq // Keep track of MST edges and total weight int mstWeight = 0; std::vector<std::pair<typename Graph<V,E>::Vertex, typename Graph<V,E>::Vertex>> mstEdges; // 5. Repeatedly pick the smallest edge from pq, and if it leads to // an unvisited vertex, add it to the MST while (/* TODO: condition: not all vertices visited */ && !pq.empty()) { // Extract top from priority queue auto [w, fromV, toV] = pq.top(); pq.pop(); // If toV is not visited, then this edge is accepted in MST if (!visited[toV]) { visited[toV] = true; // record the edge mstEdges.push_back({fromV, toV}); mstWeight += w; // For every edge from 'toV' to its neighbors: // If neighbor is unvisited, push (weight, toV, neighbor) into pq // TODO: implement } } std::cout << "Prim MST edges:\n"; for (auto& ePair : mstEdges) { auto [u, v] = ePair; std::cout << *u << " -- " << *v << "\n"; } std::cout << "Total MST Weight = " << mstWeight << std::endl; } int main() { Graph<std::string,std::string> g(false); auto A = g.insert_vertex("A"); auto B = g.insert_vertex("B"); auto C = g.insert_vertex("C"); auto D = g.insert_vertex("D"); g.insert_edge(A, B, 1); g.insert_edge(A, C, 4); g.insert_edge(B, C, 2); g.insert_edge(B, D, 5); g.insert_edge(C, D, 3); prim_mst(g); return 0; } Submit

   Answer: here

   Google doc