Drink tea and make things

Minimum Spanning Tree

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[0]); 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(); } }
Code language: JavaScript (javascript)

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *