Kruskal's Algorithm

Kruskal's Algorithm

Welcome to Kruskal's Algorithm, another powerful greedy algorithm for finding a Minimum Spanning Tree (MST) in a weighted, undirected graph. While Prim's algorithm grows a single tree, Kruskal's builds the MST by starting with a "forest" of individual vertices and progressively merging them.

---

1. The Core Idea: Building a Forest

Kruskal's algorithm takes a different approach. It sorts all the edges in the graph by weight in ascending order. Then, it iterates through the sorted edges and adds each edge to the MST if and only if adding it does not form a cycle.

This process gradually connects the initially disconnected vertices, merging them into larger and larger components, until a single spanning tree is formed.

---

2. The Role of Disjoint Set Union (DSU)

How do we efficiently check if adding an edge will form a cycle? This is where the Disjoint Set Union (DSU) data structure (also known as Union-Find) becomes essential.

• Concept: A DSU manages a collection of disjoint sets. It provides two main operations:

  • find(i): Determines which set an element i belongs to.
  • union(i, j): Merges the sets containing elements i and j.

• Application in Kruskal's: We can treat each vertex as being in its own set. For an edge (u, v), if find(u) and find(v) return the same set, it means u and v are already connected, and adding the edge would form a cycle. If they are in different sets, we can safely add the edge and then union their sets.

---

3. The Algorithm Step-by-Step

1. Initialization:

   • Create a list of all edges in the graph.
   • Sort the edges by weight in non-decreasing order.
   • Initialize a DSU data structure with N sets, one for each vertex.
   • Create an empty list to store the edges of the MST.

2. Building the MST:

   • Iterate through the sorted edges (u, v) with weight w:
     • If find(u) is not equal to find(v):
       • Add the edge (u, v) to the MST list.
       • Perform union(u, v).

3. Completion:

   • The algorithm terminates when N-1 edges have been added to the MST.

---

4. Implementation with DSU

// Assumes a DSU class is available
class DSU {
  constructor(n) { this.parent = Array.from({ length: n }, (_, i) => i); }
  find(i) {
    if (this.parent[i] === i) return i;
    return this.parent[i] = this.find(this.parent[i]); // Path compression
  }
  union(i, j) {
    const rootI = this.find(i);
    const rootJ = this.find(j);
    if (rootI !== rootJ) {
      this.parent[rootI] = rootJ;
      return true;
    }
    return false;
  }
}

function kruskals(N, edges) {
  // edges is an array of [u, v, weight]
  edges.sort((a, b) => a[2] - b[2]);

  const dsu = new DSU(N);
  const mstEdges = [];
  let totalCost = 0;

  for (const [u, v, weight] of edges) {
    if (dsu.union(u, v)) {
      mstEdges.push({ u, v, weight });
      totalCost += weight;
    }
  }

  return { mstEdges, totalCost };
}

---

5. Complexity Analysis

• Time Complexity: O(M log M) or O(M log N). The dominant step is sorting the edges. The DSU operations with path compression and union by rank/size are nearly constant on average.
• Space Complexity: O(N + M) to store the edges, the DSU data structure, and the resulting MST.

---

Key Takeaway: Kruskal's algorithm provides an alternative greedy strategy to find the MST. By sorting edges and using a DSU to prevent cycles, it builds the MST by merging components. It's particularly useful for sparse graphs or when the edge list is already available.