Kruskal's Algorithm Explained: Build MSTs and Optimize Graphs with Ease

#algorithms #graphtheory #mst #javascript

If you're dealing with graph optimization problems, one algorithm stands out for its elegance and efficiency:

Kruskal’s Algorithm.

It helps build a Minimum Spanning Tree (MST) — the cheapest way to connect all nodes in a graph without forming cycles.

Whether you’re prepping for interviews, studying computer science, or working on network design — this one’s a must-know.

📌 What You'll Learn:

What is a Minimum Spanning Tree (MST)?
How Kruskal’s Algorithm works (step-by-step)
Union-Find data structure explained
Real-world use cases
Time and space complexity
Full JavaScript code walkthrough

🌐 What is Kruskal's Algorithm?

Kruskal's Algorithm is a greedy algorithm that builds the MST by:

Sorting all edges by weight
Adding the lowest-weight edge that doesn’t form a cycle
Repeating until all nodes are connected

It uses the Disjoint Set Union (DSU) or Union-Find technique to efficiently detect and avoid cycles.

🔢 Code Example (JavaScript)

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

  find(u) {
    if (this.parent[u] !== u) {
      this.parent[u] = this.find(this.parent[u]);
    }
    return this.parent[u];
  }

  union(u, v) {
    const pu = this.find(u);
    const pv = this.find(v);
    if (pu !== pv) {
      this.parent[pu] = pv;
      return true;
    }
    return false;
  }
}

function kruskal(n, edges) {
  edges.sort((a, b) => a[2] - b[2]); // Sort by weight
  const ds = new DisjointSet(n);
  const mst = [];

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

  return mst;
}