The Aldous-Broder Algorithm

Background

The Aldous-Broder algorithm was developed independently by both David Aldous, a professor at UC Berkeley, and Andrei Broder, a Distinguished Scientist at Google. It is almost as simple to implement as the Binary Tree algorithm. The idea is just this: Start anywhere in the grid you want and choose a random neighbor. Move to that neighbor, and if it hasn’t previously been visited, link it to the prior cell. Repeat until every cell has been visited.

The Aldous-Broder algorithm explained and illustrated

It looks really easy on the paper, right? It’s that random walk, the aimless, directionless meandering from cell to cell, that is at the root of this algorithm’s ability to avoid being biased. Sadly, as we’ll see, it also means that it can take a long time to run. Let’s walk through it once so we can see it in action.

The algorithm can be better understood by looking at the following slides side by side.

1. We’ll start by picking a cell at random. We’ll color unvisited cells gray, and the smiley face will indicate which cell is current.

2. We need to pick a random neighbor, so let’s choose east. That neighbor hasn’t been visited yet, so we link the two cells together, and then we do the process again from that new cell.

3. Repeat the second step.

4. Again, repeat the second step.

5. Next, we choose a random neighbor, going north this time, but that cell has already been visited. That’s okay! It’s how the algorithm works. The only difference is, this time, we don’t link the two cells. We simply make the current cell the neighbor and carry on.

Note: It is not always possible to mark all the cells as visited; it can be an endless loop as well.

The algorithm has been explained with illustrations in the slides below.