Kruskal's Algorithm

Kruskal's algorithm is a popular algorithm in graph theory for finding the Minimum Spanning Tree (MST) of a connected, weighted, undirected graph. The MST connects all vertices with the minimum total edge weight and without any cycles.

Steps of Kruskal's Algorithm

1. Sort all edges in the graph in ascending order based on their weight.
2. Initialize a disjoint - set(union - find) structure, where each vertex starts in its own set.
3. Iterate through the sorted edges:

• For each edge, check if the vertices it connects belong to different sets(using the union - find structure).
  • If they are in different sets, add the edge to the MST and unite the sets to avoid cycles.

4. Repeat step 3 until there are exactly V-1 edges in the MST, whereV is the number of vertices.

Time Complexity

• Sorting the edges takes O(ElogE).
• Union - find operations(with path compression and union by rank) have nearly constant time complexity,O(E*logV).

The overall time complexity is O(ElogE) or O(Elog V), whereE is the number of edges and V is the number of vertices.

JavaScript Implementation

Below is a JavaScript implementation of Kruskal's algorithm:

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

  find(x) {
      if (this.parent[x] !== x) {
          this.parent[x] = this.find(this.parent[x]);  // Path compression
      }
      return this.parent[x];
  }

  union(x, y) {
      const rootX = this.find(x);
      const rootY = this.find(y);

      if (rootX !== rootY) {
          // Union by rank
          if (this.rank[rootX] > this.rank[rootY]) {
              this.parent[rootY] = rootX;
          } else if (this.rank[rootX] < this.rank[rootY]) {
              this.parent[rootX] = rootY;
          } else {
              this.parent[rootY] = rootX;
              this.rank[rootX]++;
          }
          return true;
      }
      return false;
  }
}

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

  for (const [u, v, weight] of edges) {
      if (uf.union(u, v)) {
          mst.push([u, v, weight]);
          if (mst.length === n - 1) break;  // MST has n-1 edges
      }
  }
  return mst;
}

// Example usage
const n = 4;  // Number of vertices
const edges = [
  [0, 1, 10],
  [0, 2, 6],
  [0, 3, 5],
  [1, 3, 15],
  [2, 3, 4]
];

console.log(kruskal(n, edges));//[ [ 2, 3, 4 ], [ 0, 3, 5 ], [ 0, 1, 10 ] ]