Minimum Spanning Tree (MST)

A Spanning Tree is a subgraph that connects all vertices without cycles and has edges = V - 1.

Minimum Spanning Tree is the spanning tree with the minimum total edge weight.

Kruskal’s Algorithm

Uses Greedy approach: select the edge with minimum weight that doesn’t create a cycle.

Algorithm

1. Sort edges by weight from smallest to largest
2. Process edges one by one
3. If edge doesn’t create a cycle, add it to MST
4. Continue until we have V-1 edges

Implementation (Using DSU)

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

class DSU {
public:
    vector<int> parent, rank_;
    
    DSU(int n) {
        parent.resize(n + 1);
        rank_.resize(n + 1, 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];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        // Union by rank
        if (rank_[px] < rank_[py]) swap(px, py);
        parent[py] = px;
        if (rank_[px] == rank_[py]) rank_[px]++;
        
        return true;
    }
};

pair<long long, vector<Edge>> kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    
    DSU dsu(n);
    long long totalWeight = 0;
    vector<Edge> mst;
    
    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            totalWeight += e.w;
            mst.push_back(e);
            
            if (mst.size() == n - 1) break;
        }
    }
    
    return {totalWeight, mst};
}

Complexity

• Time: $O(E \log E)$ (sorting edges)
• Space: $O(V)$ for DSU

Prim’s Algorithm

Uses Greedy approach: start from one vertex, expand MST by selecting edge with minimum weight.

Algorithm

1. Start from any vertex
2. Use priority queue to store edges connected to MST
3. Select edge with minimum weight to vertex not yet in MST
4. Continue until we have V vertices

Implementation

pair<long long, vector<pair<int, int>>> prim(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<bool> inMST(n, false);
    vector<int> key(n, INF);    // minimum edge weight to reach vertex
    vector<int> parent(n, -1);
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    key[start] = 0;
    pq.push({0, start});
    
    long long totalWeight = 0;
    
    while (!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();
        
        if (inMST[u]) continue;
        
        inMST[u] = true;
        totalWeight += w;
        
        for (auto [v, edgeWeight] : adj[u]) {
            if (!inMST[v] && edgeWeight < key[v]) {
                key[v] = edgeWeight;
                parent[v] = u;
                pq.push({key[v], v});
            }
        }
    }
    
    // Build MST edges
    vector<pair<int, int>> mstEdges;
    for (int i = 0; i < n; i++) {
        if (parent[i] != -1) {
            mstEdges.push_back({parent[i], i});
        }
    }
    
    return {totalWeight, mstEdges};
}

Complexity

• Time: $O((V + E) \log V)$ with priority queue
• Space: $O(V)$

Kruskal vs Prim

Condition	Use
Sparse Graph (E ≈ V)	Kruskal
Dense Graph (E ≈ V²)	Prim
Need MST edges	Kruskal (easier)
Graph is adjacency list	Prim

MST Properties

1. Uniqueness

MST is unique if all edge weights are distinct.

2. Cut Property

For any cut, the edge with minimum weight crossing the cut will be in the MST.

3. Cycle Property

For any cycle, the edge with maximum weight in the cycle will not be in the MST.

Second Best MST

Find the MST with the second smallest weight.

// Brute Force: try removing each edge in MST
long long secondBestMST(int n, vector<Edge>& edges) {
    auto [mstWeight, mstEdges] = kruskal(n, edges);
    
    long long secondBest = LLONG_MAX;
    
    for (int i = 0; i < mstEdges.size(); i++) {
        // Create edges without edge i
        vector<Edge> newEdges;
        for (auto& e : edges) {
            if (!(e.u == mstEdges[i].u && e.v == mstEdges[i].v && 
                  e.w == mstEdges[i].w)) {
                newEdges.push_back(e);
            }
        }
        
        auto [newWeight, newMST] = kruskal(n, newEdges);
        if (newMST.size() == n - 1) { // Still a spanning tree
            secondBest = min(secondBest, newWeight);
        }
    }
    
    return secondBest;
}

Maximum Spanning Tree

Change comparison to sort from largest to smallest.

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w > other.w; // Largest to smallest
    }
};

Example Problems

Problem 1: Find MST Weight

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    
    auto [totalWeight, mst] = kruskal(n, edges);
    
    if (mst.size() != n - 1) {
        cout << "IMPOSSIBLE" << endl; // Graph not connected
    } else {
        cout << totalWeight << endl;
    }
}

Problem 2: Connect Cities with Minimum Cost

// Given n cities and cost to connect each pair
// Find minimum total cost

int main() {
    int n;
    cin >> n;
    
    vector<Edge> edges;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int cost;
            cin >> cost;
            edges.push_back({i, j, cost});
        }
    }
    
    auto [totalCost, mst] = kruskal(n, edges);
    cout << totalCost << endl;
}

Problem 3: MST on Grid

// n × m grid where each cell has height
// cost to walk between cells = |height difference|
// Find minimum cost to connect all cells

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    
    auto idx = [&](int i, int j) { return i * m + j; };
    
    vector<Edge> edges;
    int dx[] = {0, 1};
    int dy[] = {1, 0};
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int d = 0; d < 2; d++) {
                int ni = i + dx[d], nj = j + dy[d];
                if (ni < n && nj < m) {
                    int cost = abs(grid[i][j] - grid[ni][nj]);
                    edges.push_back({idx(i, j), idx(ni, nj), cost});
                }
            }
        }
    }
    
    auto [totalCost, mst] = kruskal(n * m, edges);
    cout << totalCost << endl;
}

Summary

Algorithm	Best For	Complexity
Kruskal	Sparse graph, Edge list	$O(E \log E)$
Prim	Dense graph, Adj list	$O((V+E) \log V)$

💡 Tip: Kruskal + DSU is the simplest implementation and most commonly used in competitions.