DSA Kruskal’s Algorithm

DSA – Kruskal’s Algorithm (Minimum Spanning Tree)
(Concept • Steps • Example • Dry Run • Code • Complexity • Interview Tips)

Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted, undirected graph.

One-line idea:
Pick the smallest edges one by one, and never form a cycle.

1️⃣ What Problem Does Kruskal’s Algorithm Solve?

Given

A weighted, undirected graph

Find

A Minimum Spanning Tree
Minimum total edge weight
No cycles
Exactly V − 1 edges

2️⃣ When to Use Kruskal’s Algorithm

Scenario	Use Kruskal?
Sparse graph	✅ Best choice
Dense graph	⚠️ Prim preferred
Graph with negative weights	✅ Allowed
Directed graph	❌ Not applicable

3️⃣ Core Greedy Idea

Sort all edges by increasing weight
Pick the smallest edge
If it creates a cycle → skip
Continue until V − 1 edges are chosen

Cycle detection is done using Disjoint Set (Union–Find).

4️⃣ Key Concept: Disjoint Set (Union–Find)

Union–Find helps to:

Check if two vertices belong to the same component
Prevent cycles

Operations

find() → finds parent/root
union() → merges two sets

5️⃣ Step-by-Step Example

Graph (Edges with weights)

Sorted Edges

Picking Edges

Step	Edge	Action	Reason
1	2–3 (4)	✅ Add	No cycle
2	0–3 (5)	✅ Add	No cycle
3	0–2 (6)	❌ Skip	Cycle
4	0–1 (10)	✅ Add	No cycle

✔ MST completed with V−1 edges

6️⃣ Algorithm Steps

Sort all edges by weight
Initialize Disjoint Set for vertices
Traverse edges in sorted order
For each edge:
- If it connects different components → add to MST
- Else → skip
Stop when MST has V−1 edges

7️⃣ Kruskal’s Algorithm – C++ Implementation

#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 << "Total 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 << "Total MST Weight = " << mstWeight;

}

8️⃣ Time & Space Complexity

Time Complexity

(Sorting edges dominates)

Space Complexity

9️⃣ Kruskal vs Prim

Feature	Kruskal	Prim
Best for	Sparse graphs	Dense graphs
Data structure	Union–Find	Priority Queue
Sorting	Edges	Vertices
Start vertex	Not required	Required

🔟 Common Mistakes

❌ Forgetting to sort edges
❌ Not using Union–Find
❌ Applying on directed graph
❌ Confusing MST with shortest path

Interview Questions (Very Important)

Q1. Why does Kruskal pick edges in sorted order?
👉 Greedy choice ensures minimum total weight

Q2. Why Union–Find is needed?
👉 To detect cycles efficiently

Q3. Can Kruskal work with negative weights?
👉 ✅ Yes

Q4. When is MST unique?
👉 When all edge weights are distinct

Final Summary

✔ Greedy MST algorithm
✔ Sort edges → pick smallest
✔ Uses Union–Find to avoid cycles
✔ Best for sparse graphs
✔ Time complexity: O(E log E)

DSA Kruskal’s Algorithm