Introducing Prim's Algorithm

Background

The whole “minimum spanning tree” problem turns out to have lots of applications, like finding optimal ways to build out telephone lines or the best way to structure a computer network. Kruskal’s algorithm was one way to solve it, but it’s not the only way, which means that we should be able to find other algorithms that fulfill our needs.

One such algorithm, called Prim’s, adapts readily to random maze generation. We’ll take a look at how this algorithm works, and then we’ll see the two ways it is used to implement our mazes: a simplified version and a “true” version. Lastly, we’ll take a look at a closely related algorithm called the Growing Tree algorithm, which can actually be configured to behave not only like Prim’s but even Recursive Backtracker!

Prim's algorithm: explained and illustrated

Prim’s algorithm was first developed in 1930 by a Czech mathematician named Vojtěch Jarník, but it gets its name from Robert C. Prim, a computer scientist who rediscovered it independently in 1957. It works similarly to Dijkstra’s algorithm, starting at one point in the grid and then moving outward like water flowing, but in Prim’s case, it does more than just measure distances and costs. The end result of Prim’s is a fancy minimum spanning tree—or in our case, a maze.

As with Kruskal’s algorithm, Prim’s works by considering the weights (passage costs) on the connections between cells rather than on the individual cells themselves. We’ll look at how this comes together, but first, let's take a step back and consider some simplifications that make it easier to implement.