Color Flood: Wilson's Algorithm (opens in new tab)

For a randomized spanning tree, edges should be generated with a random weight, and Prim's algorithm extracts them from the frontier ordered by weight. This creates a very different tree structure that is much more similar to the uniform spanning tree generated by Wilson's algorithm.

(This comment is based on the code from this page: http://bl.ocks.org/mbostock/11159599)

Is this is a flood-fill algorithm?

Cause what I remember from back in the day when you could still watch MS Paint do the flood fill, a more efficient version fills out horizontal spans all at once, instead of growing like an ink blot.

But it looks cool.

EDIT: maybe this is one of those "use the entire RGB colour space" type of renderings? (see http://allrgb.com )

http://updates.html5rocks.com/2011/12/Transferable-Objects-L...

[1] http://people.renci.org/~borland/pdfs/RainbowColorMap_VisVie...

Each tree is selected uniformly amoug the HUGE set of possible spanning trees of this graph.

The color patterns in this algorithm vs. Prim algorithm are very different. Unlike Prim algorithm, this pattern is random and has a fractal structure.

Is there a good reason a programmer might need each UST to be equally likely?

   // Pick a location that’s not yet in the maze (if any).
    do if ((index0 = remaining.pop()) == null) return true;
    while (cells[index0] >= 0);

    // Perform a random walk starting at this location,
    previous[index0] = index0;
    walk: while (true) {
      i = index0 % width;
      j = index0 / width | 0;

      // picking a legal random direction at each step.
      direction = Math.random() * 4 | 0;
      if (direction === 0) { if (j <= 0) continue walk; --j; }
      else if (direction === 1) { if (j >= height - 1) continue walk; ++j; }
      else if (direction === 2) { if (i <= 0) continue walk; --i; }
      else { if (i >= width - 1) continue walk; ++i; }