Kruskal’s Minimum Spanning Tree Algorithm using Disjoint Set Union (DSU) + Union Find in Javascript

mst_dsu.js

/*
Kruskal’s Minimum Spanning Tree Algorithm using DSU
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. (Use union find / DSU to determine if a cycle has been formed)
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

DSU explanation: https://gist.github.com/KSoto/3300322fc2fb9b270dce2bf1e3d80cf3
*/

class DSU {
	constructor() {
		this.parents = [];
	}
	find(x) {
		if(typeof this.parents[x] != "undefined") {
			if(this.parents[x]<0) {
				return x; //x is a parent
			} else {
				//recurse until you find x's parent
				return this.find(this.parents[x]);
			}
		} else {
			// initialize this node to it's on parent (-1)
			this.parents[x]=-1;
			return x; //return the index of the parent
		}
	}
	union(x,y) {
		var xpar = this.find(x);
		var ypar = this.find(y);
		if(xpar != ypar) {
			// x's parent is now the parent of y also. 
			// if y was a parent to more than one node, then
			// all of those nodes are now also connected to x's parent.
			this.parents[xpar]+=this.parents[ypar]; 
			this.parents[ypar]=xpar;
			return false;
		} else {
			return true; //this link creates a cycle
		}
	}
	console_print() {
		console.log(this.parents);
	}
}

function find_mst(nodes,costs) {
	var mst = []; //the order of the path we need to take
	// 1. Sort all the edges in non-decreasing order of their weight.
	nodes.sort(function(a,b){ 
		return costs[nodes.indexOf(a)]-costs[nodes.indexOf(b)]; 
	});
	costs.sort(function(a,b){ return a-b });
	// 2. Pick the smallest edge.
	
	var total_min_cost = 0;
	
	var dsu = new DSU();
	for(var c=0; c<costs.length; c++) {
		if(dsu.find(nodes[c][0]) != dsu.find(nodes[c][1])) {
			// If cycle is not formed, include this edge.
			dsu.union(nodes[c][0],nodes[c][1]);
			total_min_cost+=costs[c];
			mst.push(nodes[c][0]+"->"+nodes[c][1]);
		}// Else, discard it.
	}
	console.log("total_min_cost = ",total_min_cost);
	console.log("path = ",mst);
}

var nodes = [[0, 1], [0, 4], [1, 4], [1, 3], [3, 2], [4, 2]];
var costs = [5, 100, 20, 70, 9, 17];

find_mst(nodes,costs);