🌲 Minimum Spanning Tree (MST) – Complete In-Depth Explanation

A **Minimum Spanning Tree (MST)** is a **subset of edges** in a **connected, weighted graph** that connects all vertices with the **minimum total edge weight** and **without forming cycles**.

📌 Why is MST Important?

• ✅ **Used in network design (telecommunication, electrical circuits, road networks).**
• 📡 **Essential for clustering in machine learning.**
• 🚀 **Forms the basis for algorithms like Approximate TSP.**
• 🔍 **Efficient in constructing trees with minimal cost in weighted graphs.**

📌 Understanding MST with an Example

Given the following weighted graph:

                     2       3
                  A---B---C
                  |   |   |
                1 |   4   | 6
                  |   |   |
                  D---E---F
                     5
                

The **Minimum Spanning Tree (MST)** would be:

                     2       3
                  A---B---C
                  |        
                1 |        
                  |        
                  D        
                

🔹 **Key Points**

• ✅ The MST must have exactly **V - 1 edges** (where V is the number of vertices).
• 📉 The MST must have the **minimum possible total weight**.
• 🔄 There can be **multiple valid MSTs** for a given graph.

🛠 Solution Approaches

📌 **1. Kruskal’s Algorithm (Greedy, O(E log E))**

Kruskal’s Algorithm sorts all edges by weight and adds them **one by one** while ensuring **no cycles are formed** (using Disjoint Set Union - DSU).

                struct Edge {
                    int src, dest, weight;
                };
            
                struct Graph {
                    int V, E;
                    vector edges;
                };
            
                struct DSU {
                    vector parent, rank;
            
                    DSU(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]);
                        return parent[x];
                    }
            
                    void unite(int x, int y) {
                        int rootX = find(x), rootY = find(y);
                        if (rootX != rootY) {
                            if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
                            else if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
                            else {
                                parent[rootY] = rootX;
                                rank[rootX]++;
                            }
                        }
                    }
                };
            
                void Kruskal(Graph &graph) {
                    sort(graph.edges.begin(), graph.edges.end(), [](Edge a, Edge b) {
                        return a.weight < b.weight;
                    });
            
                    DSU dsu(graph.V);
                    vector mst;
                    int mstCost = 0;
            
                    for (Edge e : graph.edges) {
                        if (dsu.find(e.src) != dsu.find(e.dest)) {
                            dsu.unite(e.src, e.dest);
                            mst.push_back(e);
                            mstCost += e.weight;
                        }
                    }
            
                    cout << "Minimum Spanning Tree Cost: " << mstCost << endl;
                    for (Edge e : mst) {
                        cout << e.src << " -- " << e.dest << " == " << e.weight << endl;
                    }
                }
                

📌 **2. Prim’s Algorithm (Greedy, O(V²) or O(E log V) with Priority Queue)**

Prim’s Algorithm starts from any node and **grows** the MST by selecting the **minimum weight edge** that connects to an already visited node.

                void Prim(vector>>& graph, int V) {
                    priority_queue, vector>, greater>> pq;
                    vector key(V, INT_MAX), parent(V, -1);
                    vector inMST(V, false);
            
                    pq.push({0, 0}); // {cost, node}
                    key[0] = 0;
            
                    while (!pq.empty()) {
                        int u = pq.top().second;
                        pq.pop();
                        inMST[u] = true;
            
                        for (auto &[v, weight] : graph[u]) {
                            if (!inMST[v] && weight < key[v]) {
                                key[v] = weight;
                                pq.push({key[v], v});
                                parent[v] = u;
                            }
                        }
                    }
            
                    for (int i = 1; i < V; i++) {
                        cout << parent[i] << " - " << i << " (weight: " << key[i] << ")\n";
                    }
                }
                

⏳ Time Complexity Analysis

🌍 Real-World Applications of MST

• 📡 **Network Design** – Laying down **minimum-cost communication cables.**
• 🚗 **Road Systems** – Designing **minimum-cost road networks.**
• 🔗 **Computer Clustering** – Connecting **servers with minimal latency.**
• 🛰 **Electric Grid Design** – Optimizing **power transmission networks.**

🔗 Next Topics

• 🌉 Kruskal’s Algorithm
• 📡 Prim’s Algorithm
• 🌍 Graph Algorithms