
Building Minimum Spanning Trees with Kruskals Algorithm in JavaScript
When designing fiber-optic networks, electrical grids, clustering pipelines, or road layouts, engineers frequently need to connect every node in a weighted graph using the smallest possible total edge weight without introducing redundant loops. A Minimum Spanning Tree (MST) guarantees that all reachable vertices belong to a single acyclic backbone while minimizing aggregate cost across every chosen link.
Kruskal's algorithm solves this problem greedily in $O(E \log E)$ time by processing edges globally in non-decreasing weight order rather than growing outward from a single starting vertex. Using a Disjoint Set Union (Union-Find) data structure equipped with path compression and union by rank, each candidate edge is tested in near-constant amortized $O(\alpha(V))$ time: if its endpoints belong to different connected components, the edge is added to the spanning tree and their sets are merged; otherwise, the edge would create a cycle and is discarded.
Example
function findParent(parent, node) {
if (parent[node] !== node) {
parent[node] = findParent(parent, parent[node]);
}
return parent[node];
}
function simpleKruskal(vertexCount, edges) {
const parent = Array.from({ length: vertexCount }, (_, i) => i);
const sorted = [...edges].sort((a, b) => a.weight - b.weight);
const mst = [];
for (const edge of sorted) {
const rootU = findParent(parent, edge.from);
const rootV = findParent(parent, edge.to);
if (rootU !== rootV) {
parent[rootU] = rootV;
mst.push(edge);
if (mst.length === vertexCount - 1) break;
}
}
return mst;
}
Implementation
/**
* Disjoint Set Union (Union-Find) with iterative path compression
* and union by rank to prevent recursion overflow on large graphs.
*/
export class DisjointSet {
#parent;
#rank;
#components;
/**
* @param {number} size Number of vertices indexed 0..size-1
*/
constructor(size) {
if (!Number.isInteger(size) || size < 0) {
throw new RangeError('DisjointSet size must be a non-negative integer.');
}
this.#parent = Int32Array.from({ length: size }, (_, index) => index);
this.#rank = new Uint8Array(size);
this.#components = size;
}
get componentCount() {
return this.#components;
}
/**
* Finds the representative root of `node` using two-pass path compression.
* @param {number} node
* @returns {number}
*/
find(node) {
if (node < 0 || node >= this.#parent.length) {
throw new RangeError(`Vertex index ${node} is out of bounds.`);
}
let root = node;
while (this.#parent[root] !== root) {
root = this.#parent[root];
}
let current = node;
while (current !== root) {
const next = this.#parent[current];
this.#parent[current] = root;
current = next;
}
return root;
}
/**
* Merges the sets containing `u` and `v`.
* @param {number} u
* @param {number} v
* @returns {boolean} True if a merge occurred, false if already connected
*/
union(u, v) {
const rootU = this.find(u);
const rootV = this.find(v);
if (rootU === rootV) {
return false;
}
if (this.#rank[rootU] < this.#rank[rootV]) {
this.#parent[rootU] = rootV;
} else if (this.#rank[rootU] > this.#rank[rootV]) {
this.#parent[rootV] = rootU;
} else {
this.#parent[rootV] = rootU;
this.#rank[rootU] += 1;
}
this.#components -= 1;
return true;
}
}
/**
* Computes the Minimum Spanning Tree (or Minimum Spanning Forest if disconnected)
* for an undirected weighted graph using Kruskal's algorithm.
*
* @param {number} vertexCount
* @param {Array<{ from: number, to: number, weight: number }>} edges
* @returns { {
* edges: Array<{ from: number, to: number, weight: number }>,
* totalWeight: number,
* isConnected: boolean,
* componentCount: number
* } }
*/
export function kruskalMST(vertexCount, edges) {
if (!Number.isInteger(vertexCount) || vertexCount < 0) {
throw new RangeError('vertexCount must be a non-negative integer.');
}
if (!Array.isArray(edges)) {
throw new TypeError('edges must be an array.');
}
if (vertexCount === 0) {
return { edges: [], totalWeight: 0, isConnected: true, componentCount: 0 };
}
for (const edge of edges) {
if (
!edge ||
!Number.isInteger(edge.from) ||
!Number.isInteger(edge.to) ||
typeof edge.weight !== 'number' ||
Number.isNaN(edge.weight)
) {
throw new TypeError('Each edge must have integer `from`, `to`, and numeric `weight`.');
}
}
const sortedEdges = [...edges].sort((a, b) => a.weight - b.weight);
const dsu = new DisjointSet(vertexCount);
const selectedEdges = [];
let totalWeight = 0;
for (const edge of sortedEdges) {
if (dsu.union(edge.from, edge.to)) {
selectedEdges.push(edge);
totalWeight += edge.weight;
if (selectedEdges.length === vertexCount - 1) {
break;
}
}
}
return {
edges: selectedEdges,
totalWeight,
isConnected: dsu.componentCount === 1,
componentCount: dsu.componentCount
};
}
// Example Usage
const networkEdges = [
{ from: 0, to: 1, weight: 4 },
{ from: 0, to: 2, weight: 3 },
{ from: 1, to: 2, weight: 1 },
{ from: 1, to: 3, weight: 2 },
{ from: 2, to: 3, weight: 4 },
{ from: 3, to: 4, weight: 2 },
{ from: 4, to: 5, weight: 6 }
];
const result = kruskalMST(6, networkEdges);
// result.totalWeight === 14
// result.isConnected === true
Main Point: Kruskal's algorithm pairs ascending edge sorting with a path-compressed Union-Find structure to construct a Minimum Spanning Tree in $O(E \log E)$ time while cleanly rejecting cycle-forming edges.
Credits
Photo by Agata Create on Unsplash