Kruskal's Algorithm
Minimum Spanning Tree (MST)

⬅ Previous Topic

Disjoint Set (Union-Find) with Union by Rank and Path Compression

Next Topic ⮕

Minimum Operations to Make Network Connected

Topic Contents

Problem Examples Solution Algorithm Code

Problem Statement

Given a connected, undirected, weighted graph with V vertices and E edges, the goal is to compute the sum of the edge weights of the Minimum Spanning Tree (MST). The MST is a subset of the edges that connects all vertices together, without any cycles, and with the minimum total edge weight.

Examples❯

Vertices (V)	Edges	MST Weight	Description
4	[(0,1,1), (0,2,3), (1,2,1), (1,3,4), (2,3,2)]	4	Edges chosen: (0-1), (1-2), (2-3)
3	[(0,1,10), (1,2,5), (0,2,15)]	15	Edges chosen: (1-2), (0-1)
5	[(0,1,1), (0,2,7), (1,2,5), (1,3,4), (2,4,6), (3,4,2)]	12	MST edges avoid cycles and select minimal weights
1	[]	0	Single node, no edges
2	[(0,1,100)]	100	Only one edge to connect the two nodes

Solution❯

Kruskal's Algorithm builds the Minimum Spanning Tree (MST) by selecting the smallest-weight edges first, ensuring that no cycles are formed. It uses the Disjoint Set Union (DSU) data structure to keep track of connected components and detect cycles efficiently.

The steps are as follows:

Sort all edges in non-decreasing order of weight.
Initialize DSU to manage disjoint sets of vertices.
Iterate through the sorted edge list:

If the current edge connects two different components, include it in the MST and union the sets.
Otherwise, skip the edge to avoid a cycle.

Repeat until the MST has V - 1 edges.

The algorithm ensures a globally optimal solution by always choosing the least expensive valid edge. It is especially efficient for sparse graphs.

Algorithm Steps

Sort all edges of the graph in increasing order of weight.
Initialize a Disjoint Set data structure (Union-Find) for all vertices.
Initialize mst_weight = 0.
Iterate over sorted edges:

For each edge (u, v, w), check if u and v belong to different sets.
If they do, add the edge to the MST and union the sets.
Add the weight w to mst_weight.

Continue until MST includes exactly V - 1 edges.
Return mst_weight as the final result.

Code

JavaScript

class DisjointSet {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(u) {
    if (this.parent[u] !== u) this.parent[u] = this.find(this.parent[u]);
    return this.parent[u];
  }
  union(u, v) {
    let pu = this.find(u), pv = this.find(v);
    if (pu === pv) return false;
    if (this.rank[pu] < this.rank[pv]) this.parent[pu] = pv;
    else if (this.rank[pu] > this.rank[pv]) this.parent[pv] = pu;
    else {
      this.parent[pv] = pu;
      this.rank[pu]++;
    }
    return true;
  }
}

function kruskalMST(V, edges) {
  edges.sort((a, b) => a[2] - b[2]);
  const dsu = new DisjointSet(V);
  let mstWeight = 0;
  let edgeCount = 0;

  for (const [u, v, w] of edges) {
    if (dsu.union(u, v)) {
      mstWeight += w;
      edgeCount++;
      if (edgeCount === V - 1) break;
    }
  }

  return mstWeight;
}

const edges = [
  [0, 1, 1],
  [0, 2, 3],
  [1, 2, 1],
  [1, 3, 4],
  [2, 3, 2]
];

console.log("MST weight:", kruskalMST(4, edges)); // Output: 4

⬅ Previous Topic

Disjoint Set (Union-Find) with Union by Rank and Path Compression

Next Topic ⮕

Minimum Operations to Make Network Connected

Overview of Techniques14
❯

Sorting6
❯

Arrays32
❯

Arrays - Binary Search28
❯

Strings18
❯

Matrix3
❯

Matrix - Binary Search5
❯

Binary Trees36
❯

Binary Search Trees14
❯

Graphs46
❯

Tries1
❯

Kruskal's Algorithm
Minimum Spanning Tree (MST)

Problem Statement

Examples❯

Solution❯

Algorithm Steps

Code

Support ProgramGuru.org❯

Kruskal's AlgorithmMinimum Spanning Tree (MST)

Problem Statement

Examples❯

Solution❯

Algorithm Steps

Code

Welcome to ProgramGuru

Support ProgramGuru.org❯

Kruskal's Algorithm
Minimum Spanning Tree (MST)