In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

Basic steps:

  1. Initialize a tree with a single vertex, chosen arbitrarily from the graph. (In the above application the most upper-left one)
  2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
  3. Repeat step 2 (until all vertices are in the tree).

Source: (wikipedia.org/wiki/Prim's_algorithm)



This algorithm is a randomized version of the depth-first search algorithm. Frequently implemented with a stack, this approach is one of the simplest ways to generate a maze using a computer. Consider the space for a maze being a large grid of cells (like a large chess board), each cell starting with four walls. Starting from a random cell, the computer then selects a random neighbouring cell that has not yet been visited. The computer removes the 'wall' between the two cells and adds the new cell to a stack (this is analogous to drawing the line on the floor). The computer continues this process, with a cell that has no unvisited neighbours being considered a dead-end. When at a dead-end it backtracks through the path until it reaches a cell with an unvisited neighbour, continuing the path generation by visiting this new, unvisited cell (creating a new junction). This process continues until every cell has been visited, causing the computer to backtrack all the way back to the beginning cell. This approach guarantees that the maze space is completely visited.

Mazes generated with a depth-first search have a low branching factor and contain many long corridors, because the algorithm explores as far as possible along each branch before backtracking.


The depth-first search algorithm of maze generation is frequently implemented using backtracking:

  1. Make the initial cell the current cell and mark it as visited
  2. While there are unvisited cells
    1. If the current cell has any neighbours which have not been visited
      1. Choose randomly one of the unvisited neighbours
      2. Push the current cell to the stack
      3. Remove the wall between the current cell and the chosen cell
      4. Make the chosen cell the current cell and mark it as visited
    2. Else if stack is not empty
      1. Pop a cell from the stack
      2. Make it the current cell

Source: (wikipedia.org/wiki/Maze_generation_algorithm)



This algorithm is a randomized version of Kruskal's algorithm.

  1. Create a list of all walls, and create a set for each cell, each containing just that one cell.
  2. For each wall, in some random order:
    1. If the cells divided by this wall belong to distinct sets:
      1. Remove the current wall.
      2. Join the sets of the formerly divided cells.

There are several data structures that can be used to model the sets of cells. An efficient implementation using a disjoint-set data structure can perform each union and find operation on two sets in nearly constant amortized time, so the running time of this algorithm is essentially proportional to the number of walls available to the maze.

It matters little whether the list of walls is initially randomized or if a wall is randomly chosen from a nonrandom list, either way is just as easy to code.

Source: (wikipedia.org/wiki/Maze_generation_algorithm)