，BFSDFS。
Goals
Practice working with graphs and graph algorithms by designing mazes using Kruskal’s algorithm, and solving them using either breadth- or depth-first searches.
In class, we have been discussing various algorithms for working with graphs, that require the use of several data structures working together. We have talked about general-purpose maze searching algorithms, like breadth- and depth-first searches, and we have talked about building minimum spanning trees on graphs.
To get a visual grasp of how these algorithms work, you are going to be building and solving mazes, like this one.
The mazes you construct should start in the upper-left corner (shown in green) and end in the lower-right corner (shown in purple). As you solve the mazes, you should color in the cells you have explored. Once you have reached the solution, you must backtrack the path from the end to the start, and draw it as well. A fully-solved maze might look like this.
Requirements
Your program should support at minimum the following features:
- Construct random mazes using Kruskal’s algorithm and Union/Find (below)
- Display the maze graphically and animate the search for the path.
- Allow the user to choose one of two algorithms for finding the path: Breadth-First Search or Depth-First Search (below).
- Provide an option for designing a new random maze.
- Allow the user to traverse the maze manually - using the keys to select the next move, preventing illegal moves and notifying the user of completion of the game.
- Display the solution path connecting the start and end, once it’s found (either automatically or by the user).
Be sure to submit documentation for your code, so the graders know how to run and play your game. As always, be sure to test your code thoroughly.
Additionally, you may attempt bells and whistles for extra credit:
Whistles
- Provide an option to toggle the viewing of the visited paths.
- Allow the user the ability to start a new maze without restarting the program.
- Keep the score of wrong moves - for either the automatic solutions or manual ones - and maybe keep statistics on which one of the two algorithms had fewer steps for each maze.
Bells
- In addition to animating the solution of the maze, also animate the construction of the maze: on each tick, show a single wall being knocked down.
- (Tricky) Construct mazes with a bias in a particular direction - a preference for horizontal or vertical corridors. (Hint: you might wish to play tricks with the edge weights here.)
- Hard! (But very cool) Instead of constructing a rectangular maze, try constructing a hexagonal one. You’ll have many of the same problems as you would with hexagonal islands from the Forbidden Island game; refer to that for details.
- Tricky Construct two intertwined mazes, and allow two players to race from their starting points to their ending points. Choosing the start points for both mazes is easy; choosing end points is harder. Even more impressive is ensuring that it’s a fair race, and both mazes have the same length path from start to finish… (Hint: how can you force Kruskal’s algorithm to produce two distinct connected mazes? Talk to an instructor if you choose to do this, and are not sure how to proceed.)
Spend careful thought planning ahead and designing your classes: if your design is too brittle, you’ll have a very hard time completing the algorithms. And as always, have fun!
Kruskal’s Algorithm for constructing Minimum Spanning Trees
Here is Kruskal’s algorithm illustrated on a particular example graph.
(The edges are drawn without directional arrows; in your mazes, every maze cell will be connected to its four neighbors, so edges are effectively undirected. Edge weights are notated as numbers on the edges.)
Kruskal’s algorithm begins by sorting the list of edges in the graph by edge weight, from shortest to longest:
(E C 15) (C D 25) (A B 30) (B E 35) (B C 40) (F D 50) (A E 50) (B F 50)
At each step we remove the shortest edge from the list and add it to the spanning tree, provided we do not introduce a cycle. In practice, this may produce many trees during the execution of the algorithm (so in fact, the algorithm produces a spanning forest while it runs), but they will eventually merge into a single spanning tree at the completion of the algorithm.
For this particular graph, we add the edges (E C 15), (C D 25), (A B 30) and (B E 35). When we try to add the edge (B C 40) we see that it would make a cycle, so this edge is not needed and we discard it. We then add edge (F D 50). This connects the last remaining unconnected node in the graph, and our spanning tree is complete. In very high-level pseudocode, the algorithm is quite short and elegant:
1
2
3
|
while (we do not yet have a complete spanning tree)
find the shortest edge that does not create a cycle
and add it to the spanning tree
|
Determining if we have a complete spanning tree is easy: for n nodes, we need n-1 edges to connect them all.
We can represent the spanning tree itself by a list of edges. Adding an edge to that list is as easy as Cons’ing it on, or adding it, depending on which representation of lists you choose to use. Finding the shortest edge is easy, since we began by sorting the list of edges by their weights. The only tricky part in this algorithm is figuring out whether a given edge creates a cycle with the edges we have already selected. For this we use the Union/Find data structure.
The Union/Find data structu㴾∍≔㹨㉥㰠⽧㹯㱦⽥㸠㱵 㵤≡≴㹲㍵㱣⽴㹩㱳⼠㹡㱬⁵㵴≡∠㹳㑥㱴⼠㹴㱥†⼨㹳㱵㵳∠∠㹧㕲㱡⽰㹮㱤⽲㹴㱩†㵩≮≲㹯㙵㱰⽳㹣㱨⼠㹮㱯㵴≥∠㹳㝰㱡⽮㸠㱴⽳㸩㰠⁵㵷≡≡㹴㠠㱷⽥㸠㱥⽬㹹㰠†㵥≲∠㹮㥯㱤⽥㹥㰠†⽴㹨㱥㵰∬∠㹵ㅮど㱯⽮㸠㱤⽯㹩㱮㵯≧≲㸮ㄠㅉ㱮⽴㹶㱥⼠㹷㱥㵨∠∠㹢ㅹ㈠㱮⽡㸠㱥⼠㹧㱲㵥∠≥㹳ㅥ㍮㱴⽡㸠㱥⽥㹮㱴㴠≴≴㹥ㅭ㑳㰠⽣㹥㰠⽣㹫㱥⽤㹲ഠ⁴†⁴⁹†㱡⽲㹩൮ਠ⁴††㱵㵣≫≩㹦ഠੴ⁹†⁶†⁴㰠㹥㰠㵴≩≬㹥䡭䴮㬍Ɽ‽䔢㭬䙡䕥㬳㰾⼍㹉㱮⽡㹳㱳†㵳≥∠㹥㽶㽥㽲㭮㬠⁴㬠⽳⼠䄠⁷Ɱ†㱩⽧㹴㰬⁴⽲㹩㱮㵬≬≩㹮㱯⽮㹥㱮†⽹㹯㱵㴠≴≭㹥ⁱ㱥⽡㹥㱬⽮㸠㱡㴠≣≥㹲⡥†⥥㱮⼠㹵㱮⼭㹦㱩㵲≵≥㸠⁷⁈㵰†⁴⁰⁴㱮⽯㹯㰠⽥㸠㱮㵮≯≨㹡⁴†䥩†⡩⁴⁉⥹㰠⽮㹮㱡†⽩㹳㰠㵩≴∬㸠⁴㱴⼠㹹㰠⽥㸠㱩㵲≥≥㹮⁴䕴†䥥⡭††⥬㩹㰬⼠㸠㱩⽳㸠㱮㵥≤≡㹮⁹⁴‾⡵䙧䕥Ⱪ⥮㭤㰭⽤㹳㱴⽴㹵㱲㴾≐≮㹧†⁴䕨㩮㱩⽯㹮㱤⽴㹡㰠㵴≯≫㸼 ′‾䘍⁰†㨻㱳⼠㹲㱩⼠㹮㱥㵮∯∠㹤⁴†⁴䅲⁴⁴㱩⽣㹬㱹⽮㹮㱥㵯≮∬㸠†††⡯ⵥ㭤⥥䙥䕧⁴㰼⼯㸼㱰⽩㹧㱵⽲㹬ൡੳ‽•⁴㰠⽰㹩൮ਢ‾ ‼⁴㱥⼾㸠ഠਠ†‼⁴㱯⽤㸠ഠਠ㰠⼠㸾ਊ㰠⼠㸠㰠⼠㸼൴㰠㹬♡㭧㱵⽴㹥൲ਢ㰾㸊†䘠䔼‾‽ ‼‾⁰• ‼ⴽ″‼ⴼ••‾‼†‽ ⰼ‽ ⱬ•‾ ⰾ‼ •⸼⁰䭡♳㭥‾ⰼ‾‾ ⠠••⥳䱮‼⽣‽ⰼ ‼†‾‱⁰‼‾⁰†Ⱐ†‾†††††‼‼•⁴⁓㱥⽰㹥sentatives;
To find a representative: if a node name maps to itself, then it is the representative; otherwise, “follow the links” in the representatives map, and recursively look up the representative for the current node’s parent.
To union two representatives, simply set the value of one representative’s representative to the other.
As we worked through in class, breadth- and depth-first searches are very closely related algorithms. The essential steps of the algorithm are the same; the only difference is whether to use a queue or a stack.