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
andMaze.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!
Sincerely,
P.S. It's time for a haiku: