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.

Examples❯

Graph (Edges)	Vertices	MST Weight	Description
[(0,1,1), (1,2,2), (0,2,3)]	3	3	Choose edges (0-1) and (1-2); skip (0-2) to avoid cycle
[(0,1,10), (0,2,6), (0,3,5), (1,3,15), (2,3,4)]	4	19	MST includes edges (2-3), (0-3), (0-1)
[]	0	0	Empty graph, no vertices or edges
[(0,1,5)]	2	5	Only one edge, automatically forms MST
[(0,1,1), (1,2,1), (0,2,2), (2,3,1), (3,4,1), (2,4,3)]	5	4	MST includes (0-1), (1-2), (2-3), (3-4)

Solution❯

To find the Minimum Spanning Tree (MST), we need to ensure that all nodes in the graph are connected using the minimum possible sum of edge weights without forming any cycles.

There are two popular greedy algorithms used to construct MSTs:

1. Kruskal’s Algorithm

Sort all edges in increasing order of their weight.
Initialize an empty set to store MST edges.
Use a Disjoint Set Union (DSU) to detect cycles.
Add edges one by one, skipping those that form a cycle.

2. Prim’s Algorithm

Start from any vertex and grow the MST by selecting the minimum-weight edge that connects a new vertex to the already included set.
Maintain a priority queue (min-heap) to get the minimum edge efficiently.
Repeat until all vertices are included in the MST.

Both algorithms guarantee an MST if the graph is connected and undirected. Kruskal’s is better for sparse graphs, while Prim’s performs well on dense graphs using an efficient priority queue.

Algorithm Steps❯

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).
Create a data structure to keep track of connected components (DSU) or visited vertices.
Iteratively select the minimum weight edge that connects new vertices (no cycles in Kruskal, no revisits in Prim).
Add this edge to the MST set and update your structure.
Repeat until the MST includes exactly V - 1 edges, where V is the number of vertices.

Code

JavaScript

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));

⬅ Previous TopicFind the City With the Fewest Reachable Neighbours

Next Topic ⮕Prim's Algorithm for Minimum Spanning Tree