Wilson's Algorithm

Background

Wilson’s algorithm was developed by David Bruce Wilson, a principal researcher at Microsoft and an affiliate associate professor of mathematics at the University of Washington. Like Aldous-Broder, this algorithm depends on the idea of a random walk but with a twist. It performs what is called a loop-erased random walk, which means that as it goes, if the path it is forming happens to intersect with itself and form a loop, it erases that loop before continuing on.

Wilson’s algorithm explained and illustrated

The algorithm starts by choosing a point on the grid—any point—and marking it visited. Then it chooses any unvisited cell in the ...