Understanding the Growing Tree Algorithm

The Growing Tree algorithm

Both versions of Prim’s algorithm start at an arbitrary cell, and both grow outward from that cell by selecting neighboring cells. In the case of the simplified version, neighboring cells are selected at random. For the “true” version, cells are selected based on their cost.

But those are hardly the only two ways to select cells from that list. What if we always tried to select the cell nearest to the starting point? Or the cell that was most recently added to the list? Or what if we were to combine multiple conditions somehow, picking at random half the time and picking based on weight the other half of the time?

What we have here is the basis of the Growing Tree algorithm. It works like this:

1. Choose a cell at random from the grid. Add it to the active list.

2. Choose a cell from the active list.

3. Choose a ...