Clean Markup

Building Minimum Spanning Trees with Kruskals Algorithm in JavaScript

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

← Home