Disjoint-set implementation (with path compression and ranks heuristic).
$ npm i disjointset
var DisjointSet = require('disjointset');
var edges = [
{ v: 0, u: 1, w: 7 },
{ v: 0, u: 3, w: 5 },
{ v: 1, u: 2, w: 8 },
{ v: 1, u: 3, w: 9 },
{ v: 1, u: 4, w: 7 },
{ v: 2, u: 4, w: 5 },
{ v: 3, u: 4, w: 15 },
{ v: 3, u: 5, w: 6 },
{ v: 4, u: 5, w: 8 },
{ v: 4, u: 6, w: 9 },
{ v: 5, u: 6, w: 11 }
];
// n - vertices count
function kruskal(edges, n) {
var edges = edges.sort(function(a, b) { return a.w - b.w }),
set = new DisjointSet(n),
mst = [];
edges.forEach(function(e) {
if (!set.isConnected(e.u, e.v)) {
set.union(e.u, e.v);
mst.push(e);
}
});
return mst;
}
Another example – find groups of elements with connectivity defined by fn
(see optimised variant):
function subsets(items, fn) {
var set = new DisjointSet(items.length),
roots = set.roots,
result = [];
for (var i = 0, len = items.length; i < len; i++) {
for (var j = i + 1; j < len; j++) {
if (!set.isConnected(i, j) && fn(items[i], items[j])) {
set.union(i, j);
}
}
(result[roots[i]] || (result[roots[i]] = [])).push(items[i]);
}
return result.filter(Boolean);
}
new DisjointSet(size)
isConnected(node1, node2)
union(node1, node2)
find(node)
MIT