Exercise: Modified Prim's Algorithm

We saw how the original Prim's algorithm works and implemented a Simplified Prim's algorithm and a True Prim's algorithm. There are many other variations available, though. Let's implement one.

Problem statement

Implement a modified Prim's algorithm.

The algorithm describes three sets: in, frontier, and out. Start with a random cell and place it in the frontier set. All other cells are in the out set. The in set is initially empty.

Then, while the frontier set contains any cells at all, do the following:

1. Remove a random cell from the frontier set.

2. Add the cell to the in set.

3. Pick a random neighbor of that cell, which is in the in set. (There may not be one; for the first cell, there will not be any other cells in the in set.) Link the cell to that neighbor.

4. Add all out neighbors of the cell to the frontier set.