Prim’s Algorithm

Prim’s algorithm generates a minimum spanning tree from a graph with weighted edges. Starting in the bottom-left corner, the algorithm keeps a heap of the possible directions the maze could be extended (shown in pink). At each step, the maze is extended in the direction with the lowest weight, as long as doing so does not reconnect with another part of the maze. Here the edges are initialized with random weights.

Unlike Wilson’s algorithm, this does not result in a uniform spanning tree. Sometimes, random traversal is misleadingly referred to as randomized Prim’s algorithm; however, the two algorithms exhibit radically different behavior! The global structure of the maze can be more easily seen by flooding it with color.

<!DOCTYPE html>
<meta charset="utf-8">
<style>

body {
  background: #000;
}

</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>

var width = 960,
    height = 960;

var N = 1 << 0,
    S = 1 << 1,
    W = 1 << 2,
    E = 1 << 3;

var cellSize = 4,
    cellSpacing = 4,
    cellWidth = Math.floor((width - cellSpacing) / (cellSize + cellSpacing)),
    cellHeight = Math.floor((height - cellSpacing) / (cellSize + cellSpacing)),
    cells = new Array(cellWidth * cellHeight), // each cell’s edge bits
    frontier = minHeap(function(a, b) { return a.weight - b.weight; });

var canvas = d3.select("body").append("canvas")
    .attr("width", width)
    .attr("height", height);

var context = canvas.node().getContext("2d");

context.translate(
  Math.round((width - cellWidth * cellSize - (cellWidth + 1) * cellSpacing) / 2),
  Math.round((height - cellHeight * cellSize - (cellHeight + 1) * cellSpacing) / 2)
);

context.fillStyle = "white";

// Add a random cell and two initial edges.
var start = (cellHeight - 1) * cellWidth;
cells[start] = 0;
fillCell(start);
frontier.push({index: start, direction: N, weight: Math.random()});
frontier.push({index: start, direction: E, weight: Math.random()});

// Explore the frontier until the tree spans the graph.
d3.timer(function() {
  var done, k = 0;
  while (++k < 50 && !(done = exploreFrontier()));
  return done;
});

function exploreFrontier() {
  if ((edge = frontier.pop()) == null) return true;

var edge,
      i0 = edge.index,
      d0 = edge.direction,
      i1 = i0 + (d0 === N ? -cellWidth : d0 === S ? cellWidth : d0 === W ? -1 : +1),
      x0 = i0 % cellWidth,
      y0 = i0 / cellWidth | 0,
      x1,
      y1,
      d1,
      open = cells[i1] == null; // opposite not yet part of the maze

context.fillStyle = open ? "white" : "black";
  if (d0 === N) fillSouth(i1), x1 = x0, y1 = y0 - 1, d1 = S;
  else if (d0 === S) fillSouth(i0), x1 = x0, y1 = y0 + 1, d1 = N;
  else if (d0 === W) fillEast(i1), x1 = x0 - 1, y1 = y0, d1 = E;
  else fillEast(i0), x1 = x0 + 1, y1 = y0, d1 = W;

if (open) {
    fillCell(i1);
    cells[i0] |= d0, cells[i1] |= d1;
    context.fillStyle = "magenta";
    if (y1 > 0 && cells[i1 - cellWidth] == null) fillSouth(i1 - cellWidth), frontier.push({index: i1, direction: N, weight: Math.random()});
    if (y1 < cellHeight - 1 && cells[i1 + cellWidth] == null) fillSouth(i1), frontier.push({index: i1, direction: S, weight: Math.random()});
    if (x1 > 0 && cells[i1 - 1] == null) fillEast(i1 - 1), frontier.push({index: i1, direction: W, weight: Math.random()});
    if (x1 < cellWidth - 1 && cells[i1 + 1] == null) fillEast(i1), frontier.push({index: i1, direction: E, weight: Math.random()});
  }
}

function minHeap(compare) {
  var heap = {},
      array = [],
      size = 0;

heap.empty = function() {
    return !size;
  };

heap.push = function(value) {
    up(array[size] = value, size++);
    return size;
  };

heap.pop = function() {
    if (size <= 0) return;
    var removed = array[0], value;
    if (--size > 0) value = array[size], down(array[0] = value, 0);
    return removed;
  };

function up(value, i) {
    while (i > 0) {
      var j = ((i + 1) >> 1) - 1,
          parent = array[j];
      if (compare(value, parent) >= 0) break;
      array[i] = parent;
      array[i = j] = value;
    }
  }

function down(value, i) {
    while (true) {
      var r = (i + 1) << 1,
          l = r - 1,
          j = i,
          child = array[j];
      if (l < size && compare(array[l], child) < 0) child = array[j = l];
      if (r < size && compare(array[r], child) < 0) child = array[j = r];
      if (j === i) break;
      array[i] = child;
      array[i = j] = value;
    }
  }

return heap;
}

function fillCell(index) {
  var i = index % cellWidth, j = index / cellWidth | 0;
  context.fillRect(i * cellSize + (i + 1) * cellSpacing, j * cellSize + (j + 1) * cellSpacing, cellSize, cellSize);
}

function fillEast(index) {
  var i = index % cellWidth, j = index / cellWidth | 0;
  context.fillRect((i + 1) * (cellSize + cellSpacing), j * cellSize + (j + 1) * cellSpacing, cellSpacing, cellSize);
}

function fillSouth(index) {
  var i = index % cellWidth, j = index / cellWidth | 0;
  context.fillRect(i * cellSize + (i + 1) * cellSpacing, (j + 1) * (cellSize + cellSpacing), cellSize, cellSpacing);
}

d3.select(self.frameElement).style("height", height + "px");

</script>

https://d3js.org/d3.v3.min.js