KruskalsMST.ts

class TNode {
    v: number;
    parent: TNode;
    rank: number;
    weight: number;
    constructor(v: number) {
        this.v = v;
        this.parent = null;
        this.rank = 0;
        this.weight = 0;
    }
}

function find(node: TNode): TNode {
    let current = node;
    const descendents: TNode[] = [];
    while(current.parent !== null) {
        descendents.push(current);
        current = current.parent;
    }
    for (const descendent of descendents) {
        descendent.parent = current;
    }
    return current;
}

function union(node1: TNode, node2: TNode, edge: Edge) {
    const [root1, root2] = [node1, node2].map(find);
    if (root1 === root2) return root1; // in the same set
    const [smallerRoot, largerRoot] = [root1, root2].sort((a, b) => a.rank - b.rank);
    smallerRoot.parent = largerRoot;
    if (smallerRoot.rank === largerRoot.rank) largerRoot.rank += 1;
    largerRoot.weight += smallerRoot.weight + edge[2];
}

type Edge = [number, number, number];
function kruskals(gNodes: number, gFrom: number[], gTo: number[], gWeight: number[]): number {
    const disjointForest: {[key: number]: TNode} = {};
    const edgesByWeight: {[weight: number]: Edge[]} = {};
    for (let i = 0; i < gFrom.length; i++) {
        const weight = gWeight[i];
        const edge: Edge = [gFrom[i], gTo[i], weight];
        if (typeof edgesByWeight[weight] === "undefined") {
            edgesByWeight[weight] = [edge];
        } else {
            edgesByWeight[weight].push(edge);
        }
        disjointForest[gFrom[i]] = new TNode(gFrom[i]);
        disjointForest[gTo[i]] = new TNode(gTo[i]);
    }
    for (const key of Object.keys(edgesByWeight)) {
        const weight = Number.parseInt(key, 10);
        edgesByWeight[weight].sort((e1, e2) => e1[0]+e1[1]-(e2[0]+e2[1]));
    }
    for (const key of Object.keys(edgesByWeight)) {
        const weight = Number.parseInt(key, 10);
        for (const edge of edgesByWeight[weight]) {
            if (find(disjointForest[edge[0]]) !== find(disjointForest[edge[1]])) {
                union(disjointForest[edge[0]], disjointForest[edge[1]], edge);
            }
        }
    }
    const root = find(disjointForest[gFrom[0]]);
    return root.weight;
}