HOME About NCOT Documentation Social Media Mastodon Support Me

Drink tea and make things

Blog Electronics Labs ZX Spectrum Next Computer Science Z80 Homebrew Computer Arduino and Microcontrollers

Minimum Spanning Tree

Posted:

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();
  }
}

Related Content