Minimum Spanning Tree

minimum-spanning-tree: The Ultimate Cheatsheet

1. Detailed Explanation

• What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree (MST) is a subgraph of a connected, undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. It’s a tree because it has no cycles and spans all vertices (is connected).

• Why is it important and what kind of problems does it solve?

MSTs are crucial for solving problems that involve connecting a set of nodes (e.g., cities, computers, electrical components) with the lowest possible cost (e.g., cable length, construction cost, network bandwidth). They ensure that every node is reachable from every other node in the most efficient way.

Common applications include:

• Network design: Finding the cheapest way to connect computers in a network.
• Infrastructure planning: Determining the least expensive way to lay down roads, pipelines, or power lines connecting different locations.
• Clustering: Grouping similar data points together.
• Image segmentation: Separating different regions in an image.

• Core concepts, underlying principles, and key terminology:

  • Graph: A collection of vertices (nodes) connected by edges.
  • Connected Graph: A graph where there is a path between any two vertices.
  • Undirected Graph: A graph where edges have no direction (i.e., an edge between A and B is the same as an edge between B and A).
  • Weighted Graph: A graph where each edge has a numerical value associated with it (the weight).
  • Spanning Tree: A subgraph that is a tree and connects all vertices.
  • Minimum Spanning Tree (MST): A spanning tree with the minimum total edge weight.
  • Greedy Algorithm: An algorithmic paradigm that makes the locally optimal choice at each step with the hope of finding the global optimum. MST algorithms are often greedy.
  • Cut: A partition of the vertices of a graph into two non-empty subsets.
  • Crossing Edge: An edge that connects a vertex from one subset of a cut to a vertex in the other subset.
  • Safe Edge: An edge that can be added to a partially constructed MST without creating a cycle and while minimizing the cost.

2. When to Use Minimum Spanning Tree (and When Not To)

• Identify problem patterns that suggest minimum-spanning-tree is a good fit:

  • The problem requires connecting a set of nodes.
  • There are costs (weights) associated with connecting different pairs of nodes.
  • The goal is to minimize the total cost of connecting all nodes.
  • The problem specifies that all nodes must be reachable from each other.
  • The problem explicitly states that the solution should be a tree (no cycles).

• Discuss scenarios where a different data structure or algorithm would be more appropriate:

  • Shortest path problems (Dijkstra’s, Bellman-Ford, Floyd-Warshall): If the goal is to find the shortest path between two specific nodes, rather than connecting all nodes. MST finds a minimum-weight connection for all nodes.
  • Maximum flow problems (Ford-Fulkerson): If the problem involves finding the maximum amount of flow that can be sent through a network.
  • Problems requiring cycles: MST algorithms explicitly avoid cycles. If cycles are required, a different approach is needed.
  • Problems on directed graphs: Standard MST algorithms are designed for undirected graphs. For directed graphs, consider algorithms related to arborescences (directed spanning trees).
  • Dynamic connectivity (Union-Find): While Union-Find is used within Kruskal’s algorithm, if the problem only requires determining if two nodes are connected (and the graph structure is changing), a dedicated Union-Find data structure might be more efficient than repeatedly computing an MST.

3. Core Algorithm / Data Structure Template

Here’s a general template for approaching MST problems, focusing on Kruskal’s algorithm:

1. Represent the graph: Use an adjacency list or edge list (a list of (u, v, weight) tuples). Edge lists are usually preferred for Kruskal’s because sorting edges is a key step.

2. Sort the edges: Sort the edges in ascending order of their weights.

3. Initialize a Union-Find data structure: Each vertex starts in its own separate set. Union-Find will track connected components.

4. Iterate through the sorted edges:

   • For each edge (u, v, weight):
     • Check if u and v belong to the same set using find(u) and find(v).
     • If find(u) != find(v) (u and v are in different sets):
       • Add the edge (u, v) to the MST.
       • Merge the sets containing u and v using union(u, v).
     • If find(u) == find(v) (u and v are already in the same set):
       • Skip this edge to avoid creating a cycle.

5. Return the MST: The MST is the set of edges added in step 4. The total weight of the MST is the sum of the weights of the edges in the MST.

4. Code Implementations (Python, Java, C++)

Python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

def kruskal(edges, n):
    """
    Computes the Minimum Spanning Tree using Kruskal's algorithm.

    Args:
        edges: A list of tuples (u, v, weight) representing the edges.
        n: The number of vertices in the graph.

    Returns:
        A tuple: (mst_edges, mst_weight) where mst_edges is a list of tuples
        representing the edges in the MST, and mst_weight is the total weight of the MST.
    """
    edges.sort(key=lambda x: x[2])  # Sort edges by weight
    uf = UnionFind(n)
    mst_edges = []
    mst_weight = 0

    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            mst_edges.append((u, v, weight))
            mst_weight += weight
            uf.union(u, v)

    return mst_edges, mst_weight

# Example usage:
edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
n = 4  # Number of vertices
mst_edges, mst_weight = kruskal(edges, n)
print("MST Edges:", mst_edges)
print("MST Weight:", mst_weight)

Java

import java.util.*;

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

class Edge implements Comparable<Edge> {
    int src, dest, weight;

    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

public class Kruskal {
    public static List<Edge> kruskalMST(List<Edge> edges, int numVertices) {
        Collections.sort(edges); // Sort edges by weight
        UnionFind uf = new UnionFind(numVertices);
        List<Edge> mstEdges = new ArrayList<>();

        for (Edge edge : edges) {
            if (uf.find(edge.src) != uf.find(edge.dest)) {
                mstEdges.add(edge);
                uf.union(edge.src, edge.dest);
            }
        }

        return mstEdges;
    }

    public static void main(String[] args) {
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 2, 6));
        edges.add(new Edge(0, 3, 5));
        edges.add(new Edge(1, 3, 15));
        edges.add(new Edge(2, 3, 4));

        List<Edge> mst = kruskalMST(edges, 4);
        int mstWeight = 0;
        System.out.println("MST Edges:");
        for (Edge edge : mst) {
            System.out.println(edge.src + " - " + edge.dest + " : " + edge.weight);
            mstWeight += edge.weight;
        }
        System.out.println("MST Weight: " + mstWeight);
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class UnionFind {
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

private:
    vector<int> parent;
    vector<int> rank;
};

struct Edge {
    int src, dest, weight;
};

bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

vector<Edge> kruskalMST(vector<Edge>& edges, int numVertices) {
    sort(edges.begin(), edges.end(), compareEdges);
    UnionFind uf(numVertices);
    vector<Edge> mstEdges;

    for (const auto& edge : edges) {
        if (uf.find(edge.src) != uf.find(edge.dest)) {
            mstEdges.push_back(edge);
            uf.unite(edge.src, edge.dest);
        }
    }

    return mstEdges;
}

int main() {
    vector<Edge> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };

    vector<Edge> mst = kruskalMST(edges, 4);
    int mstWeight = 0;

    cout << "MST Edges:" << endl;
    for (const auto& edge : mst) {
        cout << edge.src << " - " << edge.dest << " : " << edge.weight << endl;
        mstWeight += edge.weight;
    }
    cout << "MST Weight: " << mstWeight << endl;

    return 0;
}

5. Complexity Analysis

Operation	Time Complexity	Space Complexity	Notes
Kruskal’s Algorithm (Overall)	O(E log E)	O(V + E)	Sorting edges takes O(E log E). Union-Find operations (find and union) take nearly constant time per operation (amortized O(α(V)), where α is the inverse Ackermann function, which grows extremely slowly), and are performed at most O(E) times. Therefore, the time complexity is dominated by the sorting step. Space: O(V) for Union-Find data structure, O(E) for storing edges.
Prim’s Algorithm (with Binary Heap)	O(E log V)	O(V + E)	Using a binary heap for the priority queue.
Union-Find (find)	O(α(V)) amortized	O(V)	Using path compression and union by rank, where α(V) is the inverse Ackermann function, which grows extremely slowly and is practically constant.
Union-Find (union)	O(α(V)) amortized	N/A	Using path compression and union by rank.

Best, Average, and Worst-Case Scenarios (Kruskal’s):

• Best Case: Edges are already sorted, and very few union operations are needed (the graph is already close to being a tree). Approaches O(E).
• Average Case: Edges are randomly ordered. O(E log E)
• Worst Case: Edges are in reverse sorted order, and every edge needs to be considered before forming a connected component. O(E log E)

6. Pro Tips, Tricks, and Common Pitfalls

• Pro Tips/Tricks:

  • Edge List Representation: Always represent the graph using an edge list (list of (u, v, weight) tuples) for Kruskal’s algorithm. Sorting edges is crucial, and this representation makes it easy.
  • Union-Find Optimization: Always use path compression and union by rank in your Union-Find implementation to achieve near-constant time complexity for find and union operations.
  • Sparse vs. Dense Graphs: Kruskal’s algorithm is generally preferred for sparse graphs (graphs with relatively few edges), while Prim’s algorithm (which wasn’t implemented here but is another MST algorithm) is often better for dense graphs.
  • Disjoint Set Data Structure: Understand the Disjoint Set (Union-Find) data structure thoroughly. It’s fundamental to Kruskal’s algorithm.

• Common Pitfalls:

  • Forgetting to Sort Edges: The most common mistake in Kruskal’s algorithm is forgetting to sort the edges by weight. This will lead to an incorrect MST.
  • Incorrect Union-Find Implementation: A poorly implemented Union-Find data structure (e.g., without path compression or union by rank) can significantly increase the time complexity of Kruskal’s algorithm.
  • Handling Disconnected Graphs: MST algorithms assume the graph is connected. If the graph is disconnected, the algorithm will only find a spanning tree for each connected component, not a single spanning tree for the entire graph. You might need to check for connectivity beforehand or handle each component separately.
  • Integer Overflow: If the edge weights are large, the sum of the edge weights in the MST might exceed the maximum value of an integer data type. Use a larger data type (e.g., long long in C++, long in Java, int in Python, but be aware of potential memory implications).
  • Off-by-One Errors: When indexing vertices, be careful about off-by-one errors, especially when converting between problem descriptions and code.

7. Classic Problem Examples

Example: Connecting Cities With Minimum Cost

Description: You are given an integer n representing the number of cities numbered from 1 to n. You are also given an array connections where connections[i] = [city1, city2, cost] represents the cost of connecting city1 and city2 together.

Return the minimum cost to connect all the n cities such that there is at least one path between each pair of cities. If it is impossible to connect all the cities, return -1.

High-level Approach:

1. Represent the graph: Create a list of edges from the connections array, where each edge is a tuple (city1 - 1, city2 - 1, cost). Subtract 1 from city numbers to make them 0-indexed (for easier use with arrays).

2. Apply Kruskal’s Algorithm: Use the Kruskal’s algorithm implementation (as shown in the code examples) to find the minimum spanning tree.

3. Check for Connectivity: After running Kruskal’s, verify that all cities are connected. You can do this by checking if the Union-Find data structure has only one set. If uf.find(0) is the same as uf.find(i) for all i from 1 to n-1, then all cities are connected.

4. Handle Disconnected Case: If all cities are not connected after running Kruskal’s, return -1. Otherwise, return the total weight of the MST.