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 ...