Objectives

By the end of this chapter you should be able to:

• Compare and contrast binary search tree traversal and graph traversal
• Implement Breadth First Search and Depth First Search on graphs

Graph Traversal

Two of the simplest algorithms to use when searching through graphs are breadth first and depth first search. We've seen both of these algorithms when examining binary search trees; now let's apply the same logic for graphs!

Of course, in order for us to be able to exhaustively search through a graph, we need to assume that it is connected. This simply means that there is a path between any two vertices in the graph. All of the graphs we've looked at so far have been connected, but it's not true that all graphs are connected. Here's an example of a graph that is not connected:

In this graph, any search algorithm that starts at 0 won't be able to find any of the other vertices; similarly, any algorithm that starts at one of the other vertices won't be able to find the 0 vertex.

In our algorithms for depth and breadth first search, we'll make the assumption that our graphs are connected.

Graph Traversal vs. BST traversal

Even though we can perform depth and breadth first searches on both graphs and binary search trees, there are a couple of important differences in the implementations that should be emphasized. When we implemented searching algorithms on BSTs, we made use of some assumptions on the structure of those graphs that we can no longer safely make.

First, a BST has a canonical starting place when we want to begin a search: the root node. However, a general graph may not have the same hierarchical structure as a BST, and there may not be a natural place to begin the search. So, for our searching algorithms, we'll need to specify where the search should begin.

More importantly, you'll need to deal with a problem we didn't have to worry about with binary search trees: graph cycles. With a BST, it was enough to walk down the tree and collect nodes as we found them; in general, though, we need to be careful not to add a node to our list if we've already encountered it. Since binary search trees don't have cycles, we never had to worry about revisiting a node we'd already visited, but for general graphs this is no longer the case.

In both types of search, then, we'll need to be sure that we somehow keep track of the nodes that we have already visited, so that we can be sure to only visit them once.

Now that we've outlined the differences between searching general graphs and searching BSTs, let's jump into some pseudocode.

Depth First Search

Similar to binary search trees, we will use a stack to manage nodes visited in a graph for depth first search. Our goal will be to return an array of node values in the order in which they're searched.

Given what we've learned so far about graph search, then, here's some pseudocode to help us implement depth first search:

• Create a stack and push the starting vertex on it.
• Come up with a way to mark vertices as having been visited, and mark the starting vertex as visited
• While the stack is nonempty:
  • pop a vertex off of the stack and push it into the array of vertices to be returned
  • examine all vertices adjacent to the current vertex
    • if an adjacent vertex has not been visited yet, push it into the stack and mark it as visited

Breadth First Search

As with binary search trees, the main difference between breadth first search versus depth first search on a graph is that breadth utilizes a queue, while depth utilizes a stack. Other than that, the pseudocode is basically the same:

• Create a queue and push the starting vertex on it.
• Come up with a way to mark vertices as having been visited, and mark the starting vertex as visited
• While the queue is nonempty:
  • pop a vertex off of the queue and push it into the array of vertices to be returned
  • examine all vertices adjacent to the current vertex
    • if an adjacent vertex has not been visited yet, push it into the queue and mark it as visited

Additional Resources

Stanford CS Slides

Weights

Notice here that the graphs we are traversing do not have weights. When we need to work with a weighted graph, BFS and DFS do not become optimal for traversing through a graph. Instead we need to use more sophisticated algorithms to find the 'shortest path' between two nodes so that we can optimize according to the weights of the edges. In the next section, we'll examine two common ways of finding the shortest path.

Exercises

Pseudocode is great, but implementation is even better! Complete Part II of the Graphs Exercises.