CS 2 (Winter 2021) Lab 09: DFS

This lab focuses on implementing both a recursive and an iterative depth-first search to solve mazes.

Setup

Register for the lab using grinch: https://grinch.caltech.edu/register and clone the repository as explained in the setup instructions.

Goals and Outcomes

By the end of this lab, you will…

Depth-First Search

Depth-First Search (DFS) is a powerful algorithm for traversing (or searching) through tree or graph data structures. Essentially, the idea of the algorithm is this:

This search is “Depth-First” because it travels as deep as it can into the graph before it backtracks at all; you keep exploring deeper into the graph until you can`t explore any deeper. For example, in a depth-first search on a binary tree, all children of the left of a node should get explored before any children of the right of the node (or vise versa).

In this lab we will be implementing both a recursive and an iterative DFS to solve mazes!

Maze Interface

Mazes can be seen as generalized trees; each point in the maze represents a node in the tree, and each “child” point that you can move to from that point represents the branches from that node. A leaf node, then, is a point that has no free spaces around it other than its parent point. In this lab, we will be working with a simple maze and point interface and implementing DFS solvers to complete mazes. You can find the full implementations in Maze.java and Point.java, but here`s what you really need to know:

getChildren Helper Method

Let’s start by writing a helper method that interacts directly with the maze interface. It would be very convenient to have a method that returns an array of all of the children of a given Point (i.e. all of the points that we can move to from a given point).

public static Point[] getChildren(Point point)

Returns a Point array containing all children of a given point.


You will need to interact with the north[][], east[][], south[][], and west[][] arrays to decide where you can move from the given point. Also, make sure to set each new point’s parent to the current point!

Recursive Depth-First Search

Now that we have some helper methods, we’re ready to write our first DFS! It is easier to write a Depth-First Search recursively, so we will start with that. Before we get started, here’s a few things you should know:

Iterative Depth-First Search

It is also possible to implement the DFS algorithm iteratively! The stack data structure fits perfectly for this task; we can iteratively implement DFS by continuously pushing all children of the current node on to the stack, then popping off the top of the stack to be the new current node. Because the next level of children gets pushed on top of the other children from the previous level, we explore deeper and deeper into the tree before we backtrack to other children! Here are a few quick notes:

Checking the Results on gitlab

Getting Checked Off

At the end of every lab, you will need to call over a member of course staff to review your work. Sometimes, we will ask you to think about questions that you’ll review with the person who checks you off. For this lab, please answer the following questions:

Submit OpenEndeds For Credit