GAZAR

Principal Engineer | Mentor
Home
Algorithm
Kruskal Algorithm

Kruskal Algorithm

Kruskal Algorithm

Minimum spanning trees play a vital role in network design, clustering, and optimization problems. Kruskal's Algorithm is one of the popular algorithms used to find the minimum spanning tree of a graph by greedily selecting edges with the smallest weight while avoiding cycles.

Kruskal's Algorithm works by sorting the edges of the graph based on their weights in non-decreasing order. It then iterates through the sorted edges, adding each edge to the minimum spanning tree if it does not form a cycle with the edges already selected.

class UnionFind {
    constructor(graphKeys) {
        const graphLength = graphKeys.length
        this.parent = new Array(graphLength);
        this.rank = new Array(graphLength);
        for (let i = 0; i < graphLength; i++) {
            this.parent[graphKeys[i]] = graphKeys[i];
            this.rank[i] = 0;
        }
    }

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

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) {
            if (this.rank[rootX] < this.rank[rootY]) {
                this.parent[rootX] = rootY;
            } else if (this.rank[rootX] > this.rank[rootY]) {
                this.parent[rootY] = rootX;
            } else {
                this.parent[rootY] = rootX;
                this.rank[rootX]++;
            }
        }
    }
}

function kruskal(graph) {
    const edges = [];
    const mst = [];
    const uf = new UnionFind(Object.keys(graph));
    // Populate edges array with all edges from the graph
    for (const vertex in graph) {
        for (const neighbor in graph[vertex]) {
            edges.push([vertex, neighbor, graph[vertex][neighbor]]);
        }
    }
    // Sort edges by weight in non-decreasing order
    edges.sort((a, b) => a[2] - b[2]);
    for (const edge of edges) {
        const [src, dest, weight] = edge;
        const rootSrc = uf.find(src); 
       // Convert vertex to array index (A -> 0, B -> 1, ...)
        const rootDest = uf.find(dest);
        if (rootSrc !== rootDest) {
            mst.push(edge);
            uf.union(rootSrc, rootDest);
        }
    }
    return mst;
}
// Example usage:
const graph = {
    'A': { 'B': 10, 'C': 6, 'D': 5 },
    'B': { 'A': 10, 'D': 15 },
    'C': { 'A': 6, 'D': 4 },
    'D': { 'A': 5, 'B': 15, 'C': 4 }
};

console.log(kruskal(graph));

This code snippet will output the minimum spanning tree (MST) of the provided graph using Kruskal's Algorithm.

The time complexity of Kruskal's Algorithm is O(E log V), where E is the number of edges and V is the number of vertices in the graph. This complexity arises from sorting the edges and performing union-find operations.

Kruskal's Algorithm finds applications in network design, such as connecting cities with minimal cost in transportation networks or laying down cables in communication networks.

Comments