The Growing Tree Algorithm

Let’s rewind a moment and consider again those two versions of Prim’s algorithm that we’ve looked at. Both work by starting at an arbitrary cell, and both work by then growing 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 you always tried to select the cell nearest to the starting point? Or the cell that was most recently added to the list? Or—here’s a good one—what if you were to combine multiple conditions somehow, picking at random half the time, and picking based on weight the other ...

Get Mazes for Programmers now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.