Log inSign up
mediumGeeksforGeeksNot Started

Kruskal's Algorithm

Given a weighted undirected connected graph of V vertices and E edges, compute the total weight of the Minimum Spanning Tree (MST) using Kruskal's greedy algorithm with Disjoint Set Union (DSU).

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given a weighted, undirected and connected graph with V vertices numbered 0 to V - 1 and a list of edges edges where each edge is represented as [u, v, w] (indicating an undirected edge between u and v with weight w).

Compute the total sum of weights of the edges in a Minimum Spanning Tree (MST) of the graph using Kruskal's Algorithm.

A Spanning Tree is a subgraph that connects all V vertices together with exactly V - 1 edges without containing any cycles. A Minimum Spanning Tree is a spanning tree with the minimum possible total edge weight.

---

### Examples

Example 1: ``text Input: V = 4, edges = [[0, 1, 10], [0, 2, 6], [0, 3, 5], [1, 3, 15], [2, 3, 4]] Output: 19 Explanation: Sorted edges by weight: 1. (2, 3) weight 4 -> Add (no cycle) 2. (0, 3) weight 5 -> Add (no cycle) 3. (0, 2) weight 6 -> Cycle 0-3-2 exists! Discard. 4. (0, 1) weight 10 -> Add (no cycle) Total MST weight = 4 + 5 + 10 = 19. Number of edges in MST = 3 == V - 1.

Example 2: ``text Input: V = 3, edges = [[0, 1, 5], [1, 2, 3], [0, 2, 1]] Output: 4 Explanation: Sorted: (0, 2: 1), (1, 2: 3), (0, 1: 5). Pick (0, 2) weight 1 and (1, 2) weight 3. Total weight = 1 + 3 = 4.

---

### Constraints - 1 <= V <= 10^5 - 1 <= edges.length <= 2 * 10^5 - 0 <= w <= 10^5 - Graph is connected and undirected.

Constraints:

  • 1 <= V <= 105
  • 1 <= E <= 2 * 105
  • 0 <= w <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Prove the Cut Property that guarantees greedy edge inclusion in MST.
  • Implement Kruskal's algorithm using DSU with path compression.
  • Compare performance trade-offs between Kruskal's and Prim's algorithms.
  • Write clean, idiomatic implementations in C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Connecting all computers/islands with minimum total cable/bridge length.
  • Clustering algorithms (Single-Linkage hierarchical clustering).
  • Building road networks connecting all cities with minimum total cost.

Algorithmic Decision Tree:

  • If graph is sparse (E << V2) -> Kruskal's with DSU in O(E log E).
  • If graph is dense (E ~ V2) -> Prim's algorithm with array in O(V2).

Connected Patterns:

Prim's AlgorithmDisjoint Set UnionMin Cost to Connect All Points

1. Recursive Edge Subset Spanning Tree Search

Intuition

Enumerate all combinations of V - 1 edges using recursion. Check each combination for connectivity and no cycles, recording the minimum weight sum.

Algorithm

  1. Recursively choose whether to include each edge.
  2. When exactly V - 1 edges are selected:
  3. Verify whether the selected edges connect all V vertices using BFS/DFS.
  4. If connected, compute sum of weights and update global minimum.
  5. Return the minimum weight found.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5
6using namespace std;
7
8const int INF = 1e9;
9
10void dfs(int u, const vector<vector<int>>& adj, vector<bool>& visited) {
11 visited[u] = true;
12 for (int v : adj[u]) {
13 if (!visited[v]) dfs(v, adj, visited);
14 }
15}
16
17bool isConnectedTree(int V, const vector<vector<int>>& edges, const vector<int>& chosen) {
18 vector<vector<int>> adj(V);
19 for (int idx : chosen) {
20 adj[edges[idx][0]].push_back(edges[idx][1]);
21 adj[edges[idx][1]].push_back(edges[idx][0]);
22 }
23
24 vector<bool> visited(V, false);
25 dfs(0, adj, visited);
26
27 for (bool v : visited) {
28 if (!v) return false;
29 }
30 return true;
31}
32
33void findMinST(int idx, int V, const vector<vector<int>>& edges, vector<int>& chosen, int currWeight, int& minWeight) {
34 if (chosen.size() == V - 1) {
35 if (isConnectedTree(V, edges, chosen)) {
36 minWeight = min(minWeight, currWeight);
37 }
38 return;
39 }
40 if (idx == edges.size()) return;
41
42 // Pick edge idx
43 chosen.push_back(idx);
44 findMinST(idx + 1, V, edges, chosen, currWeight + edges[idx][2], minWeight);
45 chosen.pop_back();
46
47 // Skip edge idx
48 findMinST(idx + 1, V, edges, chosen, currWeight, minWeight);
49}
50
51int main() {
52 int V = 4;
53 vector<vector<int>> edges = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}};
54 vector<int> chosen;
55 int minWeight = INF;
56 findMinST(0, V, edges, chosen, 0, minWeight);
57 cout << "Min Spanning Tree Weight (Brute Force): " << minWeight << endl;
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(C(E, V - 1) * V)
  • Space complexity: O(V + E)

2. Prim's Algorithm via Min-Heap Priority Queue

Intuition

Vertex-centric MST algorithm starting at vertex 0 and greedily adding the minimum incident edge to an unvisited node.

Algorithm

  1. Initialize min-heap storing pairs (weight, vertex).
  2. Set visited array of size V to false.
  3. Push (0, 0) into min-heap.
  4. While heap not empty and mstEdges < V:
  5. Extract minimum element (w, u).
  6. If visited[u]: continue.
  7. Mark visited[u] = true, add w to totalWeight.
  8. For each neighbor (v, weight) of u: if !visited[v], push (weight, v) to heap.
  9. Return totalWeight.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5using namespace std;
6
7int primMST(int V, const vector<vector<int>>& edges) {
8 vector<vector<pair<int, int>>> adj(V);
9 for (const auto& e : edges) {
10 adj[e[0]].push_back({e[1], e[2]});
11 adj[e[1]].push_back({e[0], e[2]});
12 }
13
14 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
15 vector<bool> visited(V, false);
16
17 pq.push({0, 0}); // {weight, node}
18 int totalWeight = 0;
19
20 while (!pq.empty()) {
21 auto [w, u] = pq.top();
22 pq.pop();
23
24 if (visited[u]) continue;
25 visited[u] = true;
26 totalWeight += w;
27
28 for (const auto& edge : adj[u]) {
29 int v = edge.first, weight = edge.second;
30 if (!visited[v]) {
31 pq.push({weight, v});
32 }
33 }
34 }
35
36 return totalWeight;
37}
38
39int main() {
40 int V = 4;
41 vector<vector<int>> edges = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}};
42 cout << "Prim's MST Weight: " << primMST(V, edges) << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O((V + E) log V)
  • Space complexity: O(V + E)

3. Kruskal's Algorithm with Disjoint Set Union (DSU)

Intuition

Sort all edges ascending by weight. Greedily add edges that connect different DSU components until V - 1 edges are selected.

Algorithm

  1. Sort all edges by weight in non-decreasing order: edges.sort((a, b) => a[2] - b[2]).
  2. Initialize DSU of size V with path compression and union by rank.
  3. Initialize totalWeight = 0, edgesCount = 0.
  4. For each edge [u, v, w] in sorted edges:
  5. If dsu.unionSets(u, v) is true (they were in different components):
  6. totalWeight += w.
  7. edgesCount++.
  8. If edgesCount == V - 1: break early.
  9. Return totalWeight.

Kruskal's Algorithm Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Sorted edges: (2-3: 4), (0-3: 5), (0-2: 6), (0-1: 10), (1-3: 15)
Visual state
Values and pointers at this exact step
table
This state table trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
Sorted list
Decision / next transition
Process edge 2-3 (weight 4)
Why this step matters

Sorted edges: (2-3: 4), (0-3: 5), (0-2: 6), (0-1: 10), (1-3: 15).

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5
6using namespace std;
7
8class DSU {
9 vector<int> parent, rank;
10public:
11 DSU(int n) : parent(n), rank(n, 0) {
12 iota(parent.begin(), parent.end(), 0);
13 }
14
15 int find(int u) {
16 if (u == parent[u]) return u;
17 return parent[u] = find(parent[u]);
18 }
19
20 bool unionSets(int u, int v) {
21 int rootU = find(u), rootV = find(v);
22 if (rootU == rootV) return false;
23 if (rank[rootU] < rank[rootV]) {
24 parent[rootU] = rootV;
25 } else if (rank[rootV] < rank[rootU]) {
26 parent[rootV] = rootU;
27 } else {
28 parent[rootV] = rootU;
29 rank[rootU]++;
30 }
31 return true;
32 }
33};
34
35int kruskalsMST(int V, vector<vector<int>>& edges) {
36 // Sort edges by weight
37 sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) {
38 return a[2] < b[2];
39 });
40
41 DSU dsu(V);
42 int totalWeight = 0;
43 int edgesCount = 0;
44
45 for (const auto& e : edges) {
46 int u = e[0], v = e[1], w = e[2];
47 if (dsu.unionSets(u, v)) {
48 totalWeight += w;
49 edgesCount++;
50 if (edgesCount == V - 1) break; // Early termination
51 }
52 }
53
54 return totalWeight;
55}
56
57int main() {
58 int V = 4;
59 vector<vector<int>> edges = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}};
60 cout << "Optimal Kruskal's MST Weight: " << kruskalsMST(V, edges) << endl;
61 return 0;
62}

Time & Space Complexity

  • Time complexity: O(E log E)
  • Space complexity: O(V)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Exhaustive Combination Search (C(E, V - 1))O(C(E, V - 1) * V)O(V)Enumerate all subsets of V - 1 edges and find the minimum weight connected tree.Combinatorial explosion of edge subsets.
2.Prim's Algorithm with Priority QueueO((V + E) log V)O(V + E)Grow MST from an arbitrary starting vertex using a min-heap of candidate edges.Heap operations per edge relaxation.
3.Kruskal's Algorithm with DSU (Optimal for Sparse)OptimalO(E log E)O(V + E)Sort all edges ascending. Use DSU to greedily include non-cyclic edges.Edge sorting step.

Common Pitfalls & Crucial Edge Cases

Sorting in descending order instead of ascending

Yields the Maximum Spanning Tree instead of Minimum.

Not stopping at V - 1 edges

Continuing to iterate through all edges after MST is complete wastes time.

Using 1-based indexing in DSU when graph is 0-indexed

Causes out-of-bounds array access.

Crucial Edge Cases to Validate:

  • Graph with multiple equal weight edges — Any valid tie-breaking yields a valid MST with the same minimum total weight.
  • V = 1, E = 0 — Returns 0.
  • Disconnected Graph — Cannot form a spanning tree; returns -1 (or spanning forest).
  • Complete Graph — Kruskal's sorts V*(V-1)/2 edges in O(V2 log V).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the Cut Property: For any cut in the graph, the minimum weight edge crossing the cut belongs to the MST.
  2. Clearly compare Kruskal's vs Prim's: Kruskal's is edge-centric (best for sparse), Prim's is vertex-centric (best for dense).
  3. Mention that O(E log E) is asymptotically identical to O(E log V) because E <= V2 implies log(E) <= 2 log(V).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is an edge (u, v) guaranteed NOT to create a cycle in the MST if dsu.find(u) != dsu.find(v)?

2.How many edges are present in a spanning tree of a connected graph with V vertices?

Back to DSA Sheet