Kruskal's Algorithm for Minimum Spanning Tree

61.2k
0

Given a connected, undirected, weighted graph with V vertices and E edges, find the total weight of a minimum spanning tree using Kruskal's algorithm.

A minimum spanning tree connects every vertex, contains no cycle, uses exactly V - 1 edges, and has minimum total edge weight. Every edge is represented as [source, destination, weight].

Example 1

Input: V = 5, edges = [[0,1,1],[1,2,2],[0,2,3],[1,3,4],[2,3,5],[3,4,6],[2,4,7]]

Output: 13

Explanation: Edges (0,1), (1,2), (1,3), and (3,4) connect all vertices with total weight 1 + 2 + 4 + 6 = 13.

Example 2

Input: V = 4, edges = [[0,1,1],[0,2,2],[1,2,2],[1,3,3],[2,3,3]]

Output: 6

Explanation: One valid MST uses edges (0,1), (0,2), and (1,3) with total weight 1 + 2 + 3 = 6.

Approach

Disjoint Set Union replaces repeated graph traversals with near-constant-time component checks. Every vertex starts as a separate component, and each accepted edge merges two components. Equal representatives identify cycle-forming edges immediately.

Path compression shortens representative chains during searches, while union by size attaches the smaller component below the larger component. Edge sorting remains the dominant cost. Prerequisite concepts include edge sorting, parent arrays, path compression, union by size, and the cut property.

Algorithm

  • Sort all edges in nondecreasing order of weight so the cheapest edges are considered first.

  • Initialize every vertex as a separate DSU component with size 1.

  • Find the representatives of both endpoints for each sorted edge.

  • Skip the edge when both endpoints have the same representative because they already belong to the same component.

  • Merge the two different components using union by size so the smaller component attaches to the larger one.

  • Add the selected edge's weight to the MST weight and increase the selected-edge count.

  • Stop when V - 1 edges have been selected because a spanning tree with V vertices contains exactly V - 1 edges.

  • Return the accumulated MST weight.

Dry Run

kruskal-mst-plain-weight-labels-dry-run

kruskal-mst-plain-weight-labels-dry-run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Function to find a component representative with path compression.
int findParent(int node, vector<int>& parent) {
if (parent[node] == node) return node;
parent[node] = findParent(parent[node], parent);
return parent[node];
}
// Function to merge two components using union by size.
bool unite(int first, int second,
vector<int>& parent, vector<int>& size) {
int rootFirst = findParent(first, parent);
int rootSecond = findParent(second, parent);
if (rootFirst == rootSecond) return false;
if (size[rootFirst] < size[rootSecond]) {
swap(rootFirst, rootSecond);
}
parent[rootSecond] = rootFirst;
size[rootFirst] += size[rootSecond];
return true;
}
public:
// Function to compute MST weight using Disjoint Set Union.
int spanningTree(int vertices, vector<vector<int>>& edges) {
// Process edges from smallest weight to largest weight.
sort(edges.begin(), edges.end(),
[](const auto& left, const auto& right) {
return left[2] < right[2];
});
// Initialize one independent component for every vertex.
vector<int> parent(vertices);
vector<int> size(vertices, 1);
iota(parent.begin(), parent.end(), 0);
int totalWeight = 0;
int selectedEdges = 0;
// Select only edges joining different components.
for (const auto& edge : edges) {
if (!unite(edge[0], edge[1], parent, size)) continue;
totalWeight += edge[2];
selectedEdges++;
if (selectedEdges == vertices - 1) break;
}
// Return the total MST weight.
return totalWeight;
}
};
// Driver function with a hard-coded graph.
int main() {
int vertices = 5;
vector<vector<int>> edges = {
{0, 1, 1}, {1, 2, 2}, {0, 2, 3}, {1, 3, 4},
{2, 3, 5}, {3, 4, 6}, {2, 4, 7}
};
Solution solution;
cout << solution.spanningTree(vertices, edges) << "\n";
return 0;
}

Complexity Analysis

Time Complexity: O(E×log E+E×α(V))
Here, V is the number of vertices and E is the number of edges in the graph. Each DSU operation takes O(α(V)) amortized time when path compression and union by size/rank are used, where α(V) is the inverse Ackermann function. This function grows extremely slowly and is practically constant for all realistic input sizes.

Space Complexity: O(V+E), sorted edges and DSU arrays store graph and component data.

Interview follow-up Questions

Yes. Sorting places negative weights first, and cycle prevention remains unchanged.

Graph

Read Similar Blogs

Graph

Find the City with the Smallest Number of Neighbors at a Threshold Distance

Given N cities numbered from 0 to N-1 , an array of bidirectional weighted roads [first, second, weight] , and a positive distanceThreshold , count the other cities reachable from every city with s...

105.7k
Graph

Dijkstra’s Algorithm

Given an undirected weighted graph with V vertices numbered from 0 to V - 1 , an edge list, and a source vertex, find the shortest distance from source to every vertex. Every edge app...

93k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.1k
Comments0