Kruskal's Algorithm (Minimum Spanning Tree) Code Implementations
Complete Kruskal's Algorithm (Minimum Spanning Tree) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Kruskal's Algorithm (Minimum Spanning Tree) Guide ยท Launch Interactive Visualizer
C++ Implementation
// Kruskal's Algorithm Implementation in C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
class UnionFind {
private:
std::vector<int> parent;
std::vector<int> rank;
public:
UnionFind(int n) : parent(n), rank(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];
}
bool unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return false;
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
};
struct Edge {
int from, to, weight;
Edge(int from, int to, int weight) : from(from), to(to), weight(weight) {}
bool operator<(const Edge& other) const {
return weight < other.weight;
}
};
class KruskalAlgorithm {
public:
static std::vector<Edge> kruskalAlgorithm(std::vector<Edge>& edges, int vertices) {
// Sort edges by weight
std::sort(edges.begin(), edges.end());
UnionFind unionFind(vertices);
std::vector<Edge> mst;
int totalWeight = 0;
for (const Edge& edge : edges) {
if (unionFind.unite(edge.from, edge.to)) {
mst.push_back(edge);
totalWeight += edge.weight;
// Early termination if we have n-1 edges
if (mst.size() == vertices - 1) {
break;
}
}
}
return mst;
}
// Kruskal's with adjacency matrix
static std::vector<Edge> kruskalWithMatrix(const std::vector<std::vector<int>>& adjacencyMatrix) {
int n = adjacencyMatrix.size();
std::vector<Edge> edges;
// Convert matrix to edge list
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (adjacencyMatrix[i][j] != 0 && adjacencyMatrix[i][j] != std::numeric_limits<int>::max()) {
edges.emplace_back(i, j, adjacencyMatrix[i][j]);
}
}
}
return kruskalAlgorithm(edges, n);
}
// Kruskal's with adjacency list
static std::vector<Edge> kruskalWithAdjacencyList(const std::unordered_map<int, std::unordered_map<int, int>>& graph) {
std::vector<Edge> edges;
std::unordered_set<int> vertices;
// Convert adjacency list to edge list
for (const auto& [from, neighbors] : graph) {
vertices.insert(from);
for (const auto& [to, weight] : neighbors) {
if (from < to) {
edges.emplace_back(from, to, weight);
}
}
}
return kruskalAlgorithm(edges, vertices.size());
}
// Kruskal's with cycle detection
static std::pair<std::vector<Edge>, std::vector<Edge>> kruskalWithCycleDetection(std::vector<Edge>& edges, int vertices) {
std::sort(edges.begin(), edges.end());
UnionFind unionFind(vertices);
std::vector<Edge> mst;
std::vector<Edge> cycles;
for (const Edge& edge : edges) {
if (unionFind.find(edge.from) == unionFind.find(edge.to)) {
cycles.push_back(edge);
} else {
unionFind.unite(edge.from, edge.to);
mst.push_back(edge);
}
}
return {mst, cycles};
}
// Calculate total weight of MST
static int calculateTotalWeight(const std::vector<Edge>& mst) {
int totalWeight = 0;
for (const Edge& edge : mst) {
totalWeight += edge.weight;
}
return totalWeight;
}
};JAVA Implementation
// Kruskal's Algorithm Implementation in Java
import java.util.*;
class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return false;
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
}
class Edge {
int from, to, weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
public class KruskalAlgorithm {
public static Map<String, Object> kruskalAlgorithm(List<Edge> edges, int vertices) {
// Sort edges by weight
edges.sort((a, b) -> Integer.compare(a.weight, b.weight));
UnionFind unionFind = new UnionFind(vertices);
List<Edge> mst = new ArrayList<>();
int totalWeight = 0;
for (Edge edge : edges) {
if (unionFind.union(edge.from, edge.to)) {
mst.add(edge);
totalWeight += edge.weight;
// Early termination if we have n-1 edges
if (mst.size() == vertices - 1) {
break;
}
}
}
Map<String, Object> result = new HashMap<>();
result.put("mst", mst);
result.put("totalWeight", totalWeight);
result.put("isComplete", mst.size() == vertices - 1);
return result;
}
// Kruskal's with adjacency matrix
public static Map<String, Object> kruskalWithMatrix(int[][] adjacencyMatrix) {
int n = adjacencyMatrix.length;
List<Edge> edges = new ArrayList<>();
// Convert matrix to edge list
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (adjacencyMatrix[i][j] != 0 && adjacencyMatrix[i][j] != Integer.MAX_VALUE) {
edges.add(new Edge(i, j, adjacencyMatrix[i][j]));
}
}
}
return kruskalAlgorithm(edges, n);
}
// Kruskal's with adjacency list
public static Map<String, Object> kruskalWithAdjacencyList(Map<Integer, Map<Integer, Integer>> graph) {
List<Edge> edges = new ArrayList<>();
Set<Integer> vertices = new HashSet<>();
// Convert adjacency list to edge list
for (Map.Entry<Integer, Map<Integer, Integer>> entry : graph.entrySet()) {
int from = entry.getKey();
vertices.add(from);
Map<Integer, Integer> neighbors = entry.getValue();
for (Map.Entry<Integer, Integer> neighborEntry : neighbors.entrySet()) {
int to = neighborEntry.getKey();
int weight = neighborEntry.getValue();
if (from < to) {
edges.add(new Edge(from, to, weight));
}
}
}
return kruskalAlgorithm(edges, vertices.size());
}
// Kruskal's with cycle detection
public static Map<String, Object> kruskalWithCycleDetection(List<Edge> edges, int vertices) {
edges.sort((a, b) -> Integer.compare(a.weight, b.weight));
UnionFind unionFind = new UnionFind(vertices);
List<Edge> mst = new ArrayList<>();
List<Edge> cycles = new ArrayList<>();
int totalWeight = 0;
for (Edge edge : edges) {
if (unionFind.find(edge.from) == unionFind.find(edge.to)) {
cycles.add(edge);
} else {
unionFind.union(edge.from, edge.to);
mst.add(edge);
totalWeight += edge.weight;
}
}
Map<String, Object> result = new HashMap<>();
result.put("mst", mst);
result.put("totalWeight", totalWeight);
result.put("cycles", cycles);
result.put("isComplete", mst.size() == vertices - 1);
return result;
}
}JAVASCRIPT Implementation
// Kruskal's Algorithm Implementation in JavaScript
class UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX === rootY) return false;
if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
return true;
}
}
function kruskalAlgorithm(edges, vertices) {
// Sort edges by weight
edges.sort((a, b) => a.weight - b.weight);
const unionFind = new UnionFind(vertices.length);
const mst = [];
let totalWeight = 0;
for (const edge of edges) {
const { from, to, weight } = edge;
if (unionFind.union(from, to)) {
mst.push(edge);
totalWeight += weight;
// Early termination if we have n-1 edges
if (mst.length === vertices.length - 1) {
break;
}
}
}
return {
mst,
totalWeight,
isComplete: mst.length === vertices.length - 1
};
}
// Kruskal's with adjacency matrix
function kruskalWithMatrix(adjacencyMatrix) {
const n = adjacencyMatrix.length;
const edges = [];
// Convert matrix to edge list
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (adjacencyMatrix[i][j] !== 0 && adjacencyMatrix[i][j] !== Infinity) {
edges.push({
from: i,
to: j,
weight: adjacencyMatrix[i][j]
});
}
}
}
return kruskalAlgorithm(edges, Array.from({ length: n }, (_, i) => i));
}
// Kruskal's with adjacency list
function kruskalWithAdjacencyList(graph) {
const edges = [];
const vertices = new Set();
// Convert adjacency list to edge list
for (const [from, neighbors] of Object.entries(graph)) {
vertices.add(parseInt(from));
for (const [to, weight] of Object.entries(neighbors)) {
if (parseInt(from) < parseInt(to)) {
edges.push({
from: parseInt(from),
to: parseInt(to),
weight: weight
});
}
}
}
return kruskalAlgorithm(edges, Array.from(vertices));
}
// Kruskal's with cycle detection
function kruskalWithCycleDetection(edges, vertices) {
edges.sort((a, b) => a.weight - b.weight);
const unionFind = new UnionFind(vertices.length);
const mst = [];
const cycles = [];
let totalWeight = 0;
for (const edge of edges) {
const { from, to, weight } = edge;
if (unionFind.find(from) === unionFind.find(to)) {
cycles.push(edge);
} else {
unionFind.union(from, to);
mst.push(edge);
totalWeight += weight;
}
}
return {
mst,
totalWeight,
cycles,
isComplete: mst.length === vertices.length - 1
};
}PYTHON Implementation
# Kruskal's Algorithm Implementation in Python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
def kruskal_algorithm(edges, vertices):
# Sort edges by weight
edges.sort(key=lambda x: x['weight'])
union_find = UnionFind(len(vertices))
mst = []
total_weight = 0
for edge in edges:
from_vertex = edge['from']
to_vertex = edge['to']
weight = edge['weight']
if union_find.union(from_vertex, to_vertex):
mst.append(edge)
total_weight += weight
# Early termination if we have n-1 edges
if len(mst) == len(vertices) - 1:
break
return {
'mst': mst,
'total_weight': total_weight,
'is_complete': len(mst) == len(vertices) - 1
}
# Kruskal's with adjacency matrix
def kruskal_with_matrix(adjacency_matrix):
n = len(adjacency_matrix)
edges = []
# Convert matrix to edge list
for i in range(n):
for j in range(i + 1, n):
if adjacency_matrix[i][j] != 0 and adjacency_matrix[i][j] != float('inf'):
edges.append({
'from': i,
'to': j,
'weight': adjacency_matrix[i][j]
})
vertices = list(range(n))
return kruskal_algorithm(edges, vertices)
# Kruskal's with adjacency list
def kruskal_with_adjacency_list(graph):
edges = []
vertices = set()
# Convert adjacency list to edge list
for from_vertex, neighbors in graph.items():
vertices.add(int(from_vertex))
for to_vertex, weight in neighbors.items():
if int(from_vertex) < int(to_vertex):
edges.append({
'from': int(from_vertex),
'to': int(to_vertex),
'weight': weight
})
return kruskal_algorithm(edges, list(vertices))
# Kruskal's with cycle detection
def kruskal_with_cycle_detection(edges, vertices):
edges.sort(key=lambda x: x['weight'])
union_find = UnionFind(len(vertices))
mst = []
cycles = []
total_weight = 0
for edge in edges:
from_vertex = edge['from']
to_vertex = edge['to']
weight = edge['weight']
if union_find.find(from_vertex) == union_find.find(to_vertex):
cycles.append(edge)
else:
union_find.union(from_vertex, to_vertex)
mst.append(edge)
total_weight += weight
return {
'mst': mst,
'total_weight': total_weight,
'cycles': cycles,
'is_complete': len(mst) == len(vertices) - 1
}
# Kruskal's for forest (multiple components)
def kruskal_forest(edges, vertices):
edges.sort(key=lambda x: x['weight'])
union_find = UnionFind(len(vertices))
mst_edges = []
total_weight = 0
for edge in edges:
from_vertex = edge['from']
to_vertex = edge['to']
weight = edge['weight']
if union_find.union(from_vertex, to_vertex):
mst_edges.append(edge)
total_weight += weight
return {
'mst_edges': mst_edges,
'total_weight': total_weight,
'components': union_find.parent
}