Minimum Spanning Tree
(MST) in Graph Theory

Problem Statement

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, undirected, and weighted graph that connects all the vertices with the minimum total edge weight and without any cycles.

The MST ensures that:

• All vertices are connected.
• The total weight of the selected edges is minimized.
• No cycles are formed (it remains a tree).

MSTs are used in various applications like network design (telephone, electrical, or computer networks), clustering, and approximations of NP-hard problems.

Algorithm Steps

1. Sort all edges of the graph in non-decreasing order of weight (Kruskal) or initialize a min-heap with edges connected to a starting vertex (Prim).
2. Create a data structure to keep track of connected components (DSU) or visited vertices.
3. Iteratively select the minimum weight edge that connects new vertices (no cycles in Kruskal, no revisits in Prim).
4. Add this edge to the MST set and update your structure.
5. Repeat until the MST includes exactly V - 1 edges, where V is the number of vertices.

Code

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
  }

  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;
    this.parent[rootY] = rootX;
    return true;
  }
}

function kruskalMST(V, edges) {
  edges.sort((a, b) => a[2] - b[2]); // Sort edges by weight
  const uf = new UnionFind(V);
  const mst = [];
  let totalWeight = 0;

  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) {
      mst.push([u, v]);
      totalWeight += w;
    }
  }

  return { totalWeight, mst };
}

const edges = [
  [0, 1, 10], [0, 2, 6], [0, 3, 5], [1, 3, 15], [2, 3, 4]
];
const V = 4;
console.log("Kruskal MST:", kruskalMST(V, edges));