# SineSoft

## Minimum Spanning Tree

##### Posted: Oct 29, 2019

As a challenge I thought I’d try to implement the Minimum Spanning Tree algorithm, and have a play with it. My code is based off the excellent Coding Train video on the same topic which you can watch here. It’s where I got the code from, and then mixed in some code from the Arrays of Objects video too.

The result is a rather pleasing moving sea of dots that will join up when they’re close to each other.

Here’s the source code, it requires P5.js to run.

``````var vertices = [];

function setup() {
createCanvas(640, 640);

for (var i = 0; i < 50; i++) {
var v = new Bubble(random(width), random(height), random(-1,1), random(-1, 1));
vertices.push(v);
}
}

function draw() {
background(115);

var reached = [];
var unreached = [];

for (var i = 0; i < vertices.length; i++) {
vertices[i].update();

unreached.push(vertices[i]);
}

reached.push(unreached);
unreached.splice(0, 1);

while (unreached.length > 0) {
var record = 10000;
var rIndex;
var uIndex;

for (var i = 0; i < reached.length; i++) {
for (var j = 0; j < unreached.length; j++) {
var v1 = reached[i];
var v2 = unreached[j];
var d = dist(v1.x, v1.y, v2.x, v2.y);

if (d < record) {
record = d;
rIndex = i;
uIndex = j;
}
}
}
line (reached[rIndex].x, reached[rIndex].y, unreached[uIndex].x, unreached[uIndex].y);

reached.push(unreached[uIndex]);
unreached.splice(uIndex, 1);
}

for (var i = 0; i < vertices.length; i++) {
vertices[i].draw();
}
}``````