Minimum Spanning Tree
function find(parent, x) {
if (parent[x] === x) return x;
return (parent[x] = find(parent, parent[x]));
}
function union(parent, a, b) {
a = find(parent, a);
b = find(parent, b);
if (a < b) {
parent[b] = a;
} else {
parent[a] = b;
}
}
function compare(parent, a, b) {
a = find(parent, a);
b = find(parent, b);
return a === b;
}
function solution(n, costs) {
let mininumCost = 0;
const sortedCosts = costs.sort((a, b) => a[2] - b[2]);
const parent = Array.from({ length: n }, (_, i) => i);
for (const [a, b, cost] of sortedCosts) {
if (!compare(parent, a, b)) {
mininumCost += cost;
union(parent, a, b);
}
}
return mininumCost;
}
solution(4, [
[0, 1, 1],
[0, 2, 2],
[1, 2, 5],
[1, 3, 1],
[2, 3, 8]
])
FileAttachment("image.png").image()
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
