×We're offering Women's Scholarships for applicants to our February class! Details here.
By the end of this chapter you should be able to:
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.
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.
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:
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:
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.
Pseudocode is great, but implementation is even better! Complete Part II of the Graphs Exercises.
When you're ready, move on to Pathfinding with Graphs