kruskal.js

function DisjoinedSets() {
    this.parent = [];
    this.rank = [];
    
    this.find = (val) => {
        if (this.parent[val] === val) {
            return val;
        } else {
            return this.find(this.parent[val]);
        }
    }
    
    this.union = (a, b) => {
        if (this.rank[a] > this.rank[b]) {
            this.parent[b] = a;
        } else if (this.rank[a] < this.rank[b]) {
            this.parent[a] = b;
        } else {
            this.parent[a] = b;
            this.rank[b]++;
        }
    }
    
    this.makeSet = (a) => {
        this.parent[a] = a
        this.rank[a] = 0
    }
}

function kruskals(gNodes, gFrom, gTo, gWeight) {
    const djs = new DisjoinedSets();
    const edges = [];
    const ans = [];
    
    for(let i=0; i<gFrom.length; i++) {
        djs.makeSet(gFrom[i])
        djs.makeSet(gTo[i])
        
        edges.push({f: gFrom[i], t: gTo[i], w: gWeight[i]});
    }
    
    edges.sort((a,b) => a.w - b.w);
    
    for(let i=0; i<edges.length; i++) {
        const root1 = djs.find(edges[i].f);
        const root2 = djs.find(edges[i].t);
        if (root1 !== root2) {
            ans.push(edges[i].w);
            djs.union(root1, root2)
        }
    }
    
    const res = ans.reduce((sum, val) => sum+val, 0)
    return res;
}