Kruskal's Minimum Spanning Tree Algorithm

Kruskal's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, undirected, and weighted graph.

Terminology

1. Spanning Tree

A spanning tree is a subset of a connected, undirected graph that contains all the vertices of the graph and is a tree (meaning it has no cycles). For a graph with V vertices, a spanning tree always has exactly V - 1 edges.

2. Minimum Spanning Tree (MST)

An MST is a spanning tree whose sum of edge weights is minimized.

How Kruskal's Algorithm Works

1. Sort all edges in non-decreasing order of their weight.
2. Initialize a Disjoint Set structure with V elements (one for each vertex).
3. Iterate through the sorted list of edges and for each edge (u, v) with weight w:
   • Find the roots of u and v using Disjoint Set.
   • If they belong to different sets (i.e. find(u) !== find(v)), then including this edge will not form a cycle.
   • Add the edge to the MST and perform union(u, v).
   • If they belong to the same set, discard the edge.
4. Stop when the MST contains exactly V - 1 edges.

Example Dry Run

Consider a graph with 4 vertices (labeled 0, 1, 2, 3) and the following weighted edges:

• (0, 1) -> Weight 10
• (0, 2) -> Weight 6
• (0, 3) -> Weight 5
• (1, 3) -> Weight 15
• (2, 3) -> Weight 4

Step 1: Sort edges by weight

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

Step 2: Build the MST

• Edge 1: (2, 3) (Weight 4).
  • find(2) is 2, find(3) is 3. (No cycle).
  • Include this edge. MST Edges = [(2, 3)]. Union sets {2, 3}.
• Edge 2: (0, 3) (Weight 5).
  • find(0) is 0, find(3) is 3 (part of {2, 3}). (No cycle).
  • Include this edge. MST Edges = [(2, 3), (0, 3)]. Union sets {0, 2, 3}.
• Edge 3: (0, 2) (Weight 6).
  • find(0) is 0, find(2) is 0 (both belong to same set {0, 2, 3}).
  • Discard this edge (would form a cycle 0-3-2-0).
• Edge 4: (0, 1) (Weight 10).
  • find(0) is 0, find(1) is 1. (No cycle).
  • Include this edge. MST Edges = [(2, 3), (0, 3), (0, 1)]. Union sets {0, 1, 2, 3}.
  • Total edges in MST = 3 (V - 1). We stop here.

Total MST Weight: 4 + 5 + 10 = 19.

JavaScript Implementation

class DisjointSet {
    constructor(n) {
        this.parent = new Array(n).fill(-1);
        this.rank = new Array(n).fill(0);
    }
 
    find(i) {
        if (this.parent[i] === -1) {
            return i;
        }
        this.parent[i] = this.find(this.parent[i]); // Path compression
        return this.parent[i];
    }
 
    union(x, y) {
        let xRoot = this.find(x);
        let yRoot = this.find(y);
 
        if (xRoot !== yRoot) {
            if (this.rank[xRoot] < this.rank[yRoot]) {
                this.parent[xRoot] = yRoot;
            } else if (this.rank[xRoot] > this.rank[yRoot]) {
                this.parent[yRoot] = xRoot;
            } else {
                this.parent[yRoot] = xRoot;
                this.rank[xRoot]++;
            }
            return true;
        }
        return false;
    }
}
 
function kruskalsMST(vertices, edges) {
    // 1. Sort edges by weight
    edges.sort((a, b) => a[2] - b[2]);
 
    const ds = new DisjointSet(vertices);
    const mst = [];
    let totalWeight = 0;
 
    for (let i = 0; i < edges.length; i++) {
        let u = edges[i][0];
        let v = edges[i][1];
        let weight = edges[i][2];
 
        // 2. Check if u and v are already connected
        if (ds.union(u, v)) {
            mst.push([u, v, weight]);
            totalWeight += weight;
 
            // Stop early if we have found V - 1 edges
            if (mst.length === vertices - 1) {
                break;
            }
        }
    }
 
    return { mst, totalWeight };
}
 
// Driver Code
const vertices = 4;
// Edges represented as [src, dest, weight]
const edges = [
    [0, 1, 10],
    [0, 2, 6],
    [0, 3, 5],
    [1, 3, 15],
    [2, 3, 4]
];
 
const result = kruskalsMST(vertices, edges);
console.log("Edges in the constructed MST:");
result.mst.forEach(edge => {
    console.log(`${edge[0]} -- ${edge[1]} == ${edge[2]}`);
});
console.log("Minimum Spanning Tree Total Weight:", result.totalWeight);
/*
Output:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Spanning Tree Total Weight: 19
*/

Complexity Analysis

• Time Complexity: O(E log E) or O(E log V)
  • Sorting all the edges takes O(E log E) time.
  • The Disjoint Set operations (find and union) take O(E * alpha(V)) time.
  • Since O(E * alpha(V)) is negligible compared to O(E log E), the overall time complexity is dominated by sorting, which is O(E log E) (equivalent to O(E log V) since E <= V^2).
• Space Complexity: O(V + E)
  • O(V) memory for the Disjoint Set parent and rank arrays.
  • O(E) memory to store and sort the edges list.