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)