CS 240: Lecture 23 - Graph Traversals

Dear students:

An era ago we started talking about graphs. These are fun because they are more than just an abstract logical structure. They model relationships.

Exercise

Last time we met we started implementing a Graph class using an adjacency matrix. We had a list of four behaviors to implement, but we only got to three of them. Let's tackle the fourth:

• Method hasPath that returns true if and only if you can reach a given vertex from another given vertex.

How might you solve this?

There is no constant-time trick to checking if a path exists. We will need to explore outward from the first vertex and see if we ever reach reach the second. There are two exhaustive exploration algorithms that we might consider: the breadth-first traversal and the depth-first traversal.

Traversing

We've examined traversal before in the context of trees. Compared to graphs, trees have it easy. There's a clear direction of flow: you start at the root and work your way down to the leaves. With graphs, there's no obvious traversal order. One could just iterate through the set of vertices. However, we tend to want to process vertices in a couple of different manners. Either we follow paths through the graph, or we visit neighborhoods.

To trace out entire paths at a time, we perform a depth-first traversal by recursively visiting the starting vertex's unvisited neighbors:

function depthVisit(from, visiteds)
  add from to visiteds
  process from, whatever that means
  
  for each of from's neighbors
    if neighbor not in visiteds
      depthVisit(neighbor, visiteds)

This method is recursive. Any state that needs to be maintained through the recursion must be carried along in parameters. The set of visited vertices is therefore included as a parameter.

To explore the local neighborhood first, we perform a bread-first traversal. Instead of immediately visiting the starting vertex's neighbors, we queue them up. Each iteration of the loop visits the vertex that's been in the queue the longest:

function breadthVisit(from)
  frontier = new queue
  enqueue from in queue
  add from to discovereds
  
  while frontier is not empty
    v = dequeue from frontier
    process from, whatever that means
    for each of v's neighbors
      if v not discovered
        add v to discovereds
        enqueue v in frontier

This method is not recursive and may not need a visiteds parameter to carry state through the traversal if you only care about searching outward from from.

If you must visit every single vertex, you need a helper method that fires off traversals from each vertex in the graph. You'll also need to maintain a set of visited vertices so you don't go back and revisit vertices. Such a traversal algorithm might look like this in pseudocode:

function traverseGraph
  visiteds = new set
  for each vertex v
    if v not in visiteds
      visit(v, visiteds)

Maze

Many computational problems don't automatically look like a graph at first blush. But you can often find one with a little imagination. Once you spot it, you can employ graph algorithms to help solve the problem.

Consider the problem of finding a path through a maze. The maze is a 2D array. Some cells are passages and others are walls. The array view of a maze makes it iterate through and draw, but not to navigate. If we instead view each cell as being a vertex having four or so neighbors, we gain some insight into how we might find a way to escape: we write a traversal.

Together we'll code up a couple of animations of maze traversals. I've already written some code to model and draw the maze, and these are the important bits we need to know to perform the traversals:

• The Maze constructor expects a width, height, and random seed.
• The traversal must start at cell (1, 1).
• A cell is marked visited by calling Maze.visitCell.
• The methods Maze.isVisited and Maze.isUnvisited report a cell's visitedness.
• The maze is redrawn by calling MazeFrame.repaintNow.
• The maze is escaped when the bottom-right cell is visited. When this happens, Maze.isEscaped returns true.

TODO

You've got a few things to do before we meet again:

See you next time!

P.S. It's time for a haiku: