## Navigating the Codebase for Kruskal’s Algorithm¶

Here are some classes that you will need for implementing Kruskal’s algorithm to generate mazes.

`graphs.Graph`

: a basic directed graph, with generic type parameters for vertex and edge types.`graphs.KruskalGraph`

: extends`Graph`

to be undirected, and adds a few more methods required by Kruskal’s algorithm.`graphs.AdjacencyListUndirectedGraph`

: an adjacency list implementation of`KruskalGraph`

.`MazeGraph`

extends this class.- There are additional
`Graph`

implementations in the test module.

`graphs.BaseEdge`

: the base edge class; always directed and weighted.`graphs.Edge`

: the primary implementation of`BaseEdge`

.`graphs.EdgeWithData`

: a`BaseEdge`

that additionally contains some extra, generic data; used by`MazeGraph`

.

`graphs.minspantrees`

: contains algorithms for finding minimum spanning trees

## Generating Mazes¶

The “remove random walls” algorithm usually ends up generating pretty poor mazes–they either remove too many walls and create trivial mazes, or remove too few and create impossible ones.

What we really want is an algorithm that:

- generates a random-looking maze
- makes sure the maze is actually solvable
- removes as few walls as possible

It turns out that we can use MST algorithms such as Prim’s and Kruskal’s to do exactly that! We’ll start this portion of the assignment by implementing Kruskal’s algorithm, and afterwards you’ll use it to generate better mazes.

### Minimum-Spanning-Tree Finder¶

`MinimumSpanningTree`

is a container for edges, where the edges are unordered since the edges of an MST don’t have any particular ordering like the edges of a path do.

Signature | Description |
---|---|

`MinimumSpanningTree<V, E>` `findMinimumSpanningTree(G graph)` | Finds and returns a minimum spanning tree for the given graph. |

Note

The generic type declaration for this interface (and some others in this assignment) is particularly nasty. Fortunately, you shouldn’t need to worry about the exact definitions while implementing the code; the only important thing to know is that `G`

is a `Graph`

, `V`

can be any object, and `E`

is a `BaseEdge`

.

### Kruskal Graph Interface¶

Signature | Description |
---|---|

`Collection<V> allVertices()` | Returns an unmodifiable collection of all vertices in the graph. |

`Collection<E> allEdges()` | Returns an unmodifiable collection of all edges in the graph. |

## Kruskal MST Finder¶

Task

Complete `KruskalMinimumSpanningTreeFinder`

, using Kruskal’s algorithm to implement the `MinimumSpanningTreeFinder`

interface.

Implementation notes:

- The generic type bounds on this class require
`G`

to be a subtype of`KruskalGraph`

. - The skeleton code includes a snippet of code that sorts the edges of the given graph based on their weights, so you don’t need to worry about figuring out how to do that.
- Unlike the pseudocode from disjoint set lecture, the
`findMinimumSpanningTree`

must be able to detect when no MST exists and return the corresponding`MinimumSpanningTree`

result. See the`MinimumSpanningTreeFinder`

interface for a formal description of the behavior.

## Graphs used in tests:

Tree graph:

Graph with cycle:

Disconnected graph:

Graph with self-loop edge:

## Carving Mazes using Kruskal’s¶

Task

Implement `KruskalMazeCarver`

using `KruskalMinimumSpanningTreeFinder`

.

If we have an initial maze where there exists a wall between all adjacent rooms, we use `MazeCarver`

to determine which walls to remove. After the removal, a real maze can be formed.

The `MazeCarver`

requires subclasses to implement a single method:

Signature | Description |
---|---|

`Set<Wall>` `chooseWallsToRemove(Set<Wall> walls)` | Given a set of walls separating rooms in a maze base, returns a set of every wall that should be removed to form a maze. |

Recall our criteria from above:

- generates a random-looking maze
- makes sure the maze is actually solvable
- removes as few walls as possible

Here’s the trick: we take the maze and treat each room as a vertex and each wall as an edge. Then, we can assign each wall a random weight, and run any MST-finding algorithm.

For example, here’s a diagram of an MST that might be output for a grid-shaped maze:

By removing any wall that was a part of that MST, we end up satisfying all three criteria:

- By randomizing the wall weights, we remove random walls which satisfy criterion 1.
- An MST, by definition, will include a path from every vertex (every room) to every other one, satisfying criterion 2.
- And finally, because the MST will not have cycles, we avoid removing unnecessary edges and end up with a maze where there really is only one solution, satisfying criterion 3.

Implementation notes:

- If you aren’t sure where to start your implementation, take a look at
`MazeGraph`

,`Wall`

, and related classes. To reiterate,`Room`

s will be the vertices in the graph, and edges will represent`Wall`

s. - Use the
`Random`

object in the provided`rand`

field to generate the random edge weights. - Use the
`MinimumSpanningTreeFinder`

object in the provided`minimumSpanningTreeFinder`

field to find the minimum spanning tree.

After you finish, you can try using your code to generate some mazes by running the program and using the “Run (randomized) Kruskal” option. You should notice that although the mazes generated look much better than before, they take a bit longer to generate–we’ll address this by using a faster disjoint sets implementation.

## Optimize Kruskal’s with Disjoint Sets¶

Task

Use `UnionBySizeCompressingDisjointSets`

to speed up `KruskalMinimumSpanningTreeFinder`

.

Modify your `KruskalMinimumSpanningTreeFinder`

to use the `UnionBySizeCompressingDisjointSets`

class. You should notice that maze generation using `KruskalMazeCarver`

becomes significantly faster—almost indistinguishable from the time required by the `RandomMazeCarver`

.

## Submission¶

Now is a good time to submit since you’ve finished implementing how to generate mazes. If you’re working in a group, the partner who submits must **add the other partner as a group member** on Gradescope. Here’s a video demonstrating that process. You’ll also need to re-add group members whenever you resubmit to the same assignment, even if you already did so on a previous submission.

Warning

**Submitting the same code as another student without using Gradescope’s group feature is considered plagiarism, and may have consequences.**