Module maze_generator::prims_algorithm

Prim’s algorithm implementation

Prim’s approaches the problem from a different angle. Rather than working edgewise across the entire graph, it starts at one point, and grows outward from that point. The standard version of the algorithm works something like this:

1. Choose an arbitrary vertex from G (the graph), and add it to some (initially empty) set V.
2. Choose the edge with the smallest weight from G, that connects a vertex in V with another vertex not in V.
3. Add that edge to the minimal spanning tree, and the edge’s other vertex to V.
4. Repeat steps 2 and 3 until V includes every vertex in G.

And the result is a minimal spanning tree of G. Straightforward enough! With one little change, it becomes a suitable method for generating mazes: just change step 2 so that instead of selecting the edge with the smallest weight, you select an edge at random, as long as it bridges the so-called “frontier” of the maze (the set of edges that move from within the maze, to a cell that is outside the maze).

Explanation and credits to Jamis Buck’s Buckblog

Structs

PrimsGenerator

Generator implementation which uses the recursive-backtracking algorithm.