Recently I’ve done some micro-tests with spanning-trees in my spare time inspired by some talks I had with my good friend ditiem.

The video below is my implementation of Wilson’s algorithm.

Spanning-trees can be visualized as classic mazes, which are always pretty to look at (bonus: rainbow floodfill). But let’s forget about the maze itself. To me the majestuous beauty of this algorithm lies in the fact that it is fully unbiased:

  • If the random numbers involved are uniformly distributed, it generates an also uniformly distributed random sample in the space of all possible 2D-filling spanning-trees.
  • i.e., if the algorithm is called an infinite amount of times, all possible such mazes will be generated with equal likelihood.

Unbiasedness for the win.

Some interesting remarks could be made about how to optimize the generation time stochastically. Let’s save that discussion for another time…