MH3400 Algorithms for the Real World AY 2021/2022
Thomas Peyrin
Lab Session (week 8)
Deadline: 16.03.2022 11:59pm SGT
Complete all assignments below. Once you are done, submit the file(s) via NTU Learn. Remember to put
plenty of comments for all assignments, as this helps us to better understand your program (which might
give you higher marks).
Important!!! Make sure your scripts work properly, as we give 0 marks otherwise. Please
name the scripts according to the requirements, and upload each file separately and not in a
Zip file or similar. The submission system closes at the deadline. Hence after that, you will
get no marks for your solution.
For this lab session, you will have to program a Depth-First Search (DFS) and a Breadth-First
Search (BFS) to find paths in a maze-like graph. You can download on NTU Learn the template file
maze.py which contains the skeleton of the algorithms you have to implement.
The graph will represent a square-shaped maze, where each side is represented by the variable MAZE SIZE.
See below a maze example where MAZE SIZE=10.
+—+—+—+—+—+—+—+—+—+—+
| I | | | |
+ + +—+ + +—+ + +—+ +
| | | | | | |
+ + + + +—+ + +—+—+—+
| | | | | |
+ +—+ +—+ +—+—+ +—+ +
| | | | | | |
+ + + + + + +—+ +—+ +
| | | | | |
+ +—+—+ + +—+—+ + +—+
| | | | |
+ + +—+—+ +—+—+ +—+ +
| | | | | | |
+—+ + + + + +—+—+—+ +
| | | | | | |
+ +—+ +—+—+ + + +—+—+
| | | | | | |
+ +—+—+—+ +—+ + +—+ +
| | 0 |
+—+—+—+—+—+—+—+—+—+—+
Each cell of the maze is represented by a graph node (the node id is given by the row/column of the cell in
the maze: node id=col+row*MAZE SIZE), and each connection between two cells in the maze is represented
by an edge between the two corresponding nodes in the graph (i.e. if there is a wall in the maze, then there
is no connection between these two corresponding nodes in the graph). The graph is stored as a adjacency
list. For example, the graph in Figure 1 has 16 nodes and is stored as G.
+—+—+—+—+
| I | |
+ + + + +
| | | |
+ +—+ + +
| | | |
+—+ +—+ +
| O |
+—+—+—+—+
G = [
[4, 1], [0, 5],
[6, 3], [2, 7],
[0, 8], [1, 6],
[2, 5, 10], [3, 11],
[4, 9], [8, 13],
[6], [7, 15],
[13], [9, 12, 14],
[13, 15], [11, 14] ]
Figure 1: A maze with 16 cells, and its corresponding graph in adjacency representation.
1
Your first task is to implement the function DFS search(start node,end node) that searches for a
path using DFS from start node to end node). It will return a list of the node indexes encountered
during this path (in the path order). If no path exists, then an empty list is returned.
Your second task is to implement the function BFS search(start node,end node) that searches for
a path using BFS from start node to end node). It will return a list of the node indexes encountered
during this path (in the path order). If no path exists, then an empty list is returned.
2
