DSA Minimum Spanning Tree

DSA Minimum Spanning Tree (MST)
(Concept • Properties • Algorithms • Examples • Code • Complexity • Interview Tips)

A Minimum Spanning Tree (MST) is one of the most important graph topics in DSA and interviews.

What is a Spanning Tree?

For a connected, undirected graph:

Uses all vertices
Contains no cycles
Has exactly V − 1 edges

What is a Minimum Spanning Tree (MST)?

Among all possible spanning trees, the MST is the one with the minimum total edge weight.

In short:

Connect all vertices with minimum cost and no cycles

Where is MST Used?

✔ Network cable laying
✔ Road / railway planning
✔ Electrical grids
✔ Cluster analysis
✔ Minimum cost infrastructure design

Key Properties of MST

Exists only for connected graphs
Works on undirected graphs
No cycles allowed
If graph has V vertices → MST has V−1 edges
MST may not be unique (if weights repeat)

Example Graph

✔ MST picks lowest-weight edges without forming cycles.

Two Famous MST Algorithms

Algorithm	Best Use Case
Kruskal’s Algorithm	Sparse graphs
Prim’s Algorithm	Dense graphs

1️⃣ Kruskal’s Algorithm

Idea

Sort all edges by weight
Pick the smallest edge
Avoid cycles using Disjoint Set (Union-Find)

Steps

Sort edges by weight
Pick smallest edge
If it forms a cycle → skip
Repeat until V−1 edges

Complexity

Kruskal – C++ Code

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
};

bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}

int findParent(int v, vector<int>& parent) {
    if(parent[v] == v) return v;
    return parent[v] = findParent(parent[v], parent);
}

void unionSet(int a, int b, vector<int>& parent, vector<int>& rank) {
    a = findParent(a, parent);
    b = findParent(b, parent);
    if(rank[a] < rank[b]) parent[a] = b;
    else if(rank[a] > rank[b]) parent[b] = a;
    else parent[b] = a, rank[a]++;
}

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

    sort(edges.begin(), edges.end(), cmp);

    vector<int> parent(V), rank(V,0);
    for(int i=0;i<V;i++) parent[i] = i;

    int mstWeight = 0;
    for(auto e : edges) {
        if(findParent(e.u, parent) != findParent(e.v, parent)) {
            mstWeight += e.w;
            unionSet(e.u, e.v, parent, rank);
        }
    }

    cout << "MST Weight = " << mstWeight;
}

#include <bits/stdc++.h>

using namespace std;

struct Edge {

int u, v, w;

};

bool cmp(Edge a, Edge b) {

return a.w < b.w;

}

int findParent(int v, vector<int>& parent) {

if(parent[v] == v) return v;

return parent[v] = findParent(parent[v], parent);

}

void unionSet(int a, int b, vector<int>& parent, vector<int>& rank) {

a = findParent(a, parent);

b = findParent(b, parent);

if(rank[a] < rank[b]) parent[a] = b;

else if(rank[a] > rank[b]) parent[b] = a;

else parent[b] = a, rank[a]++;

}

int main() {

int V = 4;

vector<Edge> edges = {

{0,1,10}, {0,2,6}, {0,3,5}, {1,3,15}, {2,3,4}

};

sort(edges.begin(), edges.end(), cmp);

vector<int> parent(V), rank(V,0);

for(int i=0;i<V;i++) parent[i] = i;

int mstWeight = 0;

for(auto e : edges) {

if(findParent(e.u, parent) != findParent(e.v, parent)) {

mstWeight += e.w;

unionSet(e.u, e.v, parent, rank);

}

cout << "MST Weight = " << mstWeight;

}

2️⃣ Prim’s Algorithm

Idea

Start from any vertex
Always pick minimum weight edge connected to MST
Similar to Dijkstra, but for MST

Steps

Start from a node
Pick smallest edge connecting MST → new node
Repeat until all nodes included

Complexity

Prim – C++ Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int V = 5;
    vector<vector<pair<int,int>>> adj(V);

    adj[0] = {{1,2},{3,6}};
    adj[1] = {{0,2},{2,3},{3,8},{4,5}};
    adj[2] = {{1,3},{4,7}};
    adj[3] = {{0,6},{1,8}};
    adj[4] = {{1,5},{2,7}};

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    vector<bool> inMST(V,false);

    pq.push({0,0});
    int mstWeight = 0;

    while(!pq.empty()) {
        auto [w,u] = pq.top(); pq.pop();
        if(inMST[u]) continue;

        inMST[u] = true;
        mstWeight += w;

        for(auto [v,wt] : adj[u]) {
            if(!inMST[v]) pq.push({wt,v});
        }
    }

    cout << "MST Weight = " << mstWeight;
}

#include <bits/stdc++.h>

using namespace std;

int main() {

int V = 5;

vector<vector<pair<int,int>>> adj(V);

adj[0] = {{1,2},{3,6}};

adj[1] = {{0,2},{2,3},{3,8},{4,5}};

adj[2] = {{1,3},{4,7}};

adj[3] = {{0,6},{1,8}};

adj[4] = {{1,5},{2,7}};

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

vector<bool> inMST(V,false);

pq.push({0,0});

int mstWeight = 0;

while(!pq.empty()) {

auto [w,u] = pq.top(); pq.pop();

if(inMST[u]) continue;

inMST[u] = true;

mstWeight += w;

for(auto [v,wt] : adj[u]) {

if(!inMST[v]) pq.push({wt,v});

}

cout << "MST Weight = " << mstWeight;

}

Kruskal vs Prim

Feature	Kruskal	Prim
Graph type	Sparse	Dense
Data structure	Union-Find	Priority Queue
Sorting	Edges	Vertices
Starting node	Not needed	Required

MST vs Shortest Path

Feature	MST	Shortest Path
Goal	Min total cost	Min distance from source
Cycles	❌	Allowed
Algorithms	Kruskal, Prim	Dijkstra, Bellman-Ford

Interview Questions (Very Important)

Q1. Why MST has V−1 edges?
👉 To connect all vertices without cycles

Q2. Can MST exist in directed graph?
👉 ❌ No (standard MST is for undirected graphs)

Q3. Can MST be unique?
👉 Only if all edge weights are distinct

Final Summary

✔ MST connects all vertices with minimum cost
✔ Used in real-life network problems
✔ Two algorithms: Kruskal & Prim
✔ No cycles, exactly V−1 edges
✔ Core DSA + interview favorite

DSA Minimum Spanning Tree