Understanding the Simplified Version of Prim's Algorithm

Simplified Prim’s algorithm

Simplified versions of Prim’s algorithm are fairly common among maze generators and are typically referred to as “Prim’s algorithm” by many sources. However, unlike the real algorithm, these simplified versions do not actually bother with different costs and weights for passages. In fact, these algorithms tend to be similar to what we would get if we ran the real Prim’s algorithm on a grid in which every passage had the same cost.

Recall how the algorithm began. After picking a cell at random as the starting point, it looked for the lowest cost passage that connected to that starting cell. But if every passage had the same weight, they’d all tie, and we’d break the tie by choosing among the candidates at random.

So, if every passage in the entire grid had the same weight, Prim’s would simply choose a connecting passage at random at each step. This happens to be essentially what these simplified algorithms do, with one notable difference: instead of choosing passages, they typically choose cells.

There are several possible variations that we could implement, but we’ll stick with a simple one here. We'll create a new class called SimplifiedPrims.

The SimplifiedPrims class