Depth-First Search

The two well-known approaches for graph search are depth-first search and breadth-first search. Both approaches can get the job done, but each provides unique advantages in particular situations. We’re going to start with depth-first search, also referred to as DFS, because it’s actually quite similar to the algorithm for binary tree traversal that we discussed back in . In fact, it’s also the same essential algorithm that we saw in .

As mentioned earlier, graph search can be used to either find a particular vertex, or it can be used to simply traverse the graph. We’re going to begin by using depth-first search to traverse the graph since that algorithm is slightly simpler.

The key to any graph search algorithm is keeping track of which vertices we’ve visited so far. If we don’t do this, we can end up in an infinite cycle. Take the following graph, for example:

Here, Mohammad is friends with Felicia. And Felicia also happens to be friends with Zeina. But Zeina is friends with Mohammad. So our code would end up going in circles unless we keep track of which vertices we’ve already traversed.

This problem didn’t occur when we dealt with trees (or filesystem traversal), since trees can’t have cycles. But since a graph can have a cycle, we need to address this issue now.

One way to keep track of our visited vertices is by using a hash table. As we visit each vertex, we add the vertex (or its value) as a key in the hash table and assign it an arbitrary value, such as the Boolean True. If a vertex is present in the hash table, it means we’ve already visited it.

With this in mind, the depth-first search algorithm works as follows.

1. Start at any random vertex within the graph.

2. Add the current vertex to the hash table to mark it as having been visited.

3. Iterate through the current vertex’s adjacent vertices.

4. For each adjacent vertex, if the adjacent vertex has already been visited, ignore it.

5. If the adjacent vertex has not yet been visited, recursively perform depth-first search on that vertex.

Depth-First Search Walk-Through

Let’s see this in action.

In this walk-through, we’re going to start with Alice. In the following diagrams, the vertex with lines around it is the current vertex. A check mark means we’ve officially marked the vertex as having been visited (and added to the hash table).

Step 1: We start with Alice and give her a check mark to indicate that we’ve officially visited her vertex:

Next up, we’ll iterate over Alice’s neighbors using a loop. These will be Bob, Candy, Derek, and Elaine.

The order of which neighbor to visit first doesn’t matter, so let’s just start with Bob. He seems nice.

Step 2: We now perform depth-first search on Bob. Note that this is making a recursive call, as we’re already in the middle of a depth-first search of Alice.

As with all recursion, the computer needs to remember which function calls it’s still in the middle of, so it first adds Alice to the call stack:

We can now begin the depth-first search on Bob, which makes Bob the current vertex. We mark him as visited, as shown in the .

We then iterate over Bob’s adjacent vertices. These are Alice and Fred.

Step 3: Alice has already been visited, so we can ignore her.

Step 4: The only other neighbor, then, is Fred. We call the depth-first search function on Fred’s vertex. The computer first adds Bob to the call stack to remember that it’s still in the middle of searching Bob:

We now perform depth-first search on Fred. He’s now the current vertex, so we mark him as visited:

Next, we iterate over Fred’s adjacent vertices, which are Bob and Helen.

Step 5: Bob has already been visited, so we ignore him.

Step 6: The only remaining adjacent vertex is Helen. We recursively perform depth-search first on Helen, so the computer first adds Fred to the call stack:

We now begin depth-first search on Helen. She’s the current vertex, so we mark her as visited:

Helen has two adjacent vertices: Fred and Candy.

Step 7: We’ve already visited Fred, so we can ignore him.

Step 8: Candy has not yet been visited, so we recursively perform depth-search on Candy. First, though, Helen gets added to the call stack:

We perform depth-first search on Candy. She’s now the current vertex, and we mark her as visited:

Candy has two adjacent vertices: Alice and Helen.

Step 9: We’ve already visited Alice, so we can ignore her.

Step 10: We’ve already visited Helen, so we can ignore her as well.

Since Candy has no other neighbors, we’re done performing depth-first search on Candy. At this point, then, the computer begins to unwind the call stack.

First, it pops off Helen from the call stack. We’ve already iterated over all her neighbors, so the depth-first search on Helen is complete.

The computer pops off Fred. We’ve iterated over all his neighbors too, so we’re done searching him as well.

The computer pops off Bob, but we’re done with him as well.

The computer then pops Alice off the call stack. Within our search of Alice, we were in the middle of looping through all of Alice’s neighbors. Now, this loop already iterated over Bob. (This was Step 2.) This leaves Candy, Derek, and Elaine.

Step 11: Candy has already been visited, so there’s no need to perform search on her.

However, we’ve not yet visited Derek or Elaine.

Step 12: Let’s proceed by recursively performing depth-first search on Derek. The computer adds Alice to the call stack once again:

The depth-first search of Derek now begins. Derek is the current vertex, so we mark him as visited:

Derek has three adjacent vertices: Alice, Elaine, and Gina.

Step 13: Alice has already been visited, so we don’t need to perform another search on her.

Step 14: Let’s visit Elaine next, by recursively performing depth-first search on her vertex. Before we do, the computer adds Derek to the call stack:

We now perform depth-first search on Elaine. We mark Elaine as visited, as shown in the .

Elaine has two adjacent vertices: Alice and Derek.

Step 15: Alice has already been visited, so there’s no need to perform another search on her.

Step 16: Derek, too, has already been visited.

Since we iterated over all Elaine’s neighbors, we’re done searching Elaine. The computer now pops Derek from the call stack and loops over his remaining adjacent vertices. In this case, Gina is the final neighbor to visit.

Step 17: We’ve never visited Gina before, so we recursively perform depth-first search on her vertex. First, though, the computer adds Derek to the call stack again:

We begin our depth-first search of Gina, and mark her as visited, as shown in the .

Gina has two neighbors: Derek and Irena.

Step 18: Derek has already been visited.

Step 19: Gina has one unvisited adjacent vertex—namely, Irena. Gina gets added to the call stack so that we can recursively perform depth-first search on Irena:

We begin search on Irena and mark her as visited:

We iterate over Irena’s neighbors. Irena has only one neighbor: Gina.

Step 20: Gina has already been visited.

The computer then unwinds the call stack, popping off each vertex one by one. However, since each vertex on the call stack has already iterated over all of its neighbors, there’s nothing more for the computer to do with each vertex.

This means we’re done!

Code Implementation: Depth-First Search

Here is an implementation of depth-first traversal:

Our dfs_traverse method accepts a single vertex and a visited_vertices hash table. The first time we call this function, we pass in the empty hash table visited_vertices. For the above example, we’d perform a depth-first traversal starting with Alice, with the following:

As we visit vertices, though, we populate this hash table with the vertices we’ve visited and pass along the same hash table with each recursive call.

The first thing we do within the function is mark the current vertex as visited. We do this by adding the vertex’s value to the hash:

We then optionally print the vertex’s value just to get feedback that we’ve truly traversed it:

Next, we iterate over all the adjacent vertices of the current vertex:

We check each adjacent vertex to see whether it has already been visited. If it has, we do nothing, but if it has never been visited, we recursively call dfs_traverse on that adjacent vertex:

Again, we also pass in the visited_vertices hash table so the ensuing call has access to it.

If we want to use depth-first search to search for a particular vertex, we can use a modified version of the previous function:

This implementation also recursively calls itself for each vertex, but returns the vertex_we_are_searching_for if it finds the correct vertex.