CS 240: Lecture 23 - Graph Traversals
An era ago we started talking about graphs. These are fun because they are more than just an abstract logical structure. They model relationships.
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:
hasPaththat 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.
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
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)
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:
Mazeconstructor expects a width, height, and random seed.
- The traversal must start at cell (1, 1).
A cell is marked visited by calling
Maze.isUnvisitedreport a cell's visitedness.
The maze is redrawn by calling
The maze is escaped when the bottom-right cell is visited. When this happens,
You've got a few things to do before we meet again:
See you next time!
P.S. It's time for a haiku: