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❯

Understanding the Problem

We are given an undirected, connected graph where each edge has a weight (or cost). The goal is to construct a Minimum Spanning Tree (MST) — a subgraph that:

Connects all the vertices (no node is left out),
Uses exactly V - 1 edges (where V is the number of vertices),
Has the minimum total edge weight among all such possible trees,
Contains no cycles.

This is a classical graph problem that appears often in real-world scenarios like designing cost-effective network layouts (roads, electrical grids, etc.).

Step-by-Step Solution with Example

step 1: Choose the right algorithm

There are two common greedy algorithms for MST:

Kruskal’s Algorithm – Works by choosing the smallest edge first. Good for sparse graphs.
Prim’s Algorithm – Starts from a node and grows the MST by always selecting the smallest connecting edge. Better for dense graphs.

We’ll use Kruskal’s Algorithm for this example.

step 2: Understand the given example

Consider this graph:


Nodes: 0, 1, 2, 3
Edges:
(0 - 1, weight 10)
(0 - 2, weight 6)
(0 - 3, weight 5)
(1 - 3, weight 15)
(2 - 3, weight 4)

step 3: Sort all edges by weight

We sort the edges in ascending order of weights:

(2 - 3, weight 4)
(0 - 3, weight 5)
(0 - 2, weight 6)
(0 - 1, weight 10)
(1 - 3, weight 15)

step 4: Initialize Disjoint Set Union (DSU)

Each node is in its own set. We'll merge sets as we add edges, avoiding cycles.

step 5: Add edges one by one

Add (2 - 3, weight 4): No cycle. Add to MST.
Add (0 - 3, weight 5): No cycle. Add to MST.
Add (0 - 2, weight 6): Would create a cycle (0 connected to 3, which connects to 2). Skip.
Add (0 - 1, weight 10): No cycle. Add to MST.

MST now includes edges: (2 - 3), (0 - 3), (0 - 1). Total weight = 4 + 5 + 10 = 19

Edge Cases

Disconnected Graph: No MST is possible if the graph is not fully connected.
Multiple equal weight edges: Both Kruskal’s and Prim’s can still work as long as we prevent cycles.
Negative weights: MST algorithms handle negative weights fine as long as no cycle is formed.
Self-loops or multiple edges between same nodes: Ignore self-loops. Use the minimum weight edge between two nodes.

Finally

Finding the Minimum Spanning Tree ensures the most efficient way to connect all points in a network without redundancy. By understanding the problem and using greedy strategies like Kruskal's or Prim's, we can solve it efficiently.

Remember to visualize the graph, sort or prioritize edges properly, and use Disjoint Set (for Kruskal) or Priority Queue (for Prim) wisely. Handling edge cases ensures that your algorithm works on all types of graphs.

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

Comments

Loading comments...