This assignment covers the following topics: Greedy algorithm
Graph
A maze can be generated by starting with a predetermined arrangement of cells (most commonly a rectangular grid but other arrangements are possible) with wall sites between them. This predetermined arrangement can be considered as a connected graph with the edges representing possible wall sites and the nodes representing cells. The purpose of the maze generation algorithm can then be considered to be making a subgraph in which it is challenging to find a route between two particular nodes.
If the subgraph is not connected, then there are regions of the graph that are wasted because they do not contribute to the search space. If the graph contains loops, then there may be multiple paths between the chosen nodes. Because of this, maze generation is often approached as generating a random spanning tree.
Image missing
In this assignment, you are required to write a C++ program to generate a random maze by using Kruskal’s algorithm. Your program should have a proper data structure to store the maze generated and should also have a print function to print out the maze on the screen.
(Hint: You can use character such as ┌, ┐, └, ┘, ├, ┤, ┬, ┴, ┼, │, ─, to draw the wall)
Submission:
Use appropriate comments in your source code. Zip and upload the entire project folder to moodle on or before the due date. An extension of time may be granted in
certain circumstances. A request for an extension must be made to the Lecturer before the due date. Late submission without granted extension will be marked but the mark awarded will be reduced by 10% for each day late. Submissions will not be accepted if more than three days late.
Assessment:
Marks will be awarded based on the quality of the implemented algorithm and data structures. Note that marks may be deducted for other reasons, e.g. if your code is too messy or inefficient, is not well commented, etc.
For code that does not compile, does not work or for programs that crash, the most you can get is half the marks (i.e. 5 marks or less). Note that you may be contacted to explain your code.
