Insight 34.7.1.
Depth-first search locks in edges in the search tree when a vertex is selected to be explored. Breadth-first search locks in edges when a vertex is first discovered.
Section 34.7 Depth-First Search
While breadth-first search explores the graph in layers, depth-first search explores the graph by going as deep as possible down one path before backtracking. It does so by storing a stack of vertices to be explored. At each step, it removes the top item from the stack and explores all of its neighbors that have not yet been explored. Those neighbors are added to the top of the stack to be explored later.
Below is the pseudocode for depth-first search:
DFS(graph, start):
Stack searchStack
searchStack.push(start)
Map parentMap
Set visitedSet
visitedSet.insert(start)
while not searchStack.isEmpty():
vertex = searchStack.pop()
if not visitedSet.contains(vertex):
visitedSet.insert(vertex)
for each neighbor of vertex:
if not visitedSet.contains(neighbor):
parentMap[neighbor] = vertex
searchStack.push(neighbor)
Key differences between depth-first search and the breadth-first search algorithm we saw earlier include:
-
Depth-first search uses a stack while breadth-first search uses a queue. (Line 2)
-
DFS does not mark a node as visited until it is popped from the stack. (Line 11) In contrast, breadth-first search marked a node as “known” as soon as it was discovered.
The second item means that DFS may add the same vertex to the stack multiple times if it is reachable from multiple paths. Each time we “see” a vertex, we will change its parent to be the vertex we are currently exploring. We won’t lock in that choice until the vertex is popped from the stack and marked as visited. In contrast, breadth-first search locked in the parent of a vertex as soon as it was discovered.
Exploration 34.7.1.
A depth-first search over a graph.
(a)
We will do a depth-first search over the graph shown below starting from vertex 1. To do so we add 1 to the search stack.
Current search stack (top at front):
[1]
(b)
Remove the top element from the search stack: 1. Get the list of neighbors of 1. For each neighbor that we have not explored yet, add it to the search stack and remember that we will reach it from 1.
We will push the neighbors of 1 (2, 3, and 5) onto the search stack in reverse order (5, 3, 2) so that they are explored in numeric order.
Current search stack (top at front):
[2 3 5]
(c)
Remove the top element from the search stack: 2. Get the list of neighbors of 2. For each neighbor that we have not explored yet, add it to the search stack and remember that we will reach it from 2.
The only neighbor of 2 that we have not yet explored is 0. Push it onto the search stack and remember that we will reach it from 2.
Current search stack (top at front):
[0 3 5]
(d)
Remove the top element from the search stack: 0. Get the list of neighbors of 0. For each neighbor that we have not explored yet, add it to the search stack and remember that we will reach it from 0.
We have explored all neighbors of 0.
Current search stack (top at front):
[3 5]
Not adding anything to the stack represents hitting a dead end in the search tree and backtracking to explore a different path.
(e)
Remove the top element from the search stack: 3. Get the list of neighbors of 3. For each neighbor that we have not explored yet, add it to the search stack and remember that we will reach it from 3.
We have explored 1 already. But we have not explored 7, so push it onto the search stack and remember that we will reach it from 3.
Current search stack (top at front):
[7 5]
(f)
Remove the top element from the search stack: 7. Get the list of neighbors of 7. For each neighbor that we have not explored yet, add it to the search stack and remember that we will reach it from 7.
We have explored 3 already. But we have not explored 4, 5, or 6 so push them onto the search stack and remember that we will reach them from 7. Note that this means we have “changed our minds” about how to reach 5. Before we thought we would reach 5 from 1, but now we know we will reach it from 7.
Current search stack (top at front):
[4 5 6 5]
The search stack contains multiple copies of 5, because we have seen 5 from both 1 and 7.
(g)
Remove the top element from the search stack: 4. Get the list of neighbors of 4. For each neighbor that we have not explored yet, add it to the search stack and remember that we will reach it from 4.
We have explored 7 already. But we have not explored 5, so push it onto the search stack and remember that we will reach it from 5.
Current search stack (top at front):
[5 5 6 5]
Yet again, we have changed our minds about how to reach 5. We now believe we will reach 5 from 4. It appears on the stack multiple times, once for each time we have seen it from a different vertex.
(h)
Remove the top element from the search stack: 5. Get the list of neighbors of 5. For each neighbor that we have not explored yet, add it to the search stack and remember that we will reach it from 5.
We have explored 4 and 7 already.
Current search stack (top at front):
[5 6 5]
(i)
Remove the top element from the search stack: 5. Since we have already explored 5, we will continue to the next element in the search stack.
Current search stack (top at front):
[6 5]
Remove the top element from the search stack: 6. Get the list of neighbors of 6. For each neighbor that we have not explored yet, add it to the search stack and remember that we will reach it from 6.
We have explored 7 already.
Current search stack (top at front):
[5]
At this point we would continue popping elements from the search stack until it is empty. All the remaining elements have already been explored.
Below is the final search tree rendered in the original graph and as a standalone tree. The depth-first search produced a search tree with longer chains because it keeps going in one direction as long as it can, repeatedly changing its mind about how to reach certain vertices. Thus a depth-first search generally does not produce the shortest path between vertices in the search tree.
The search tree is not unique. If we had added neighbors to the search stack in a different order, we would have produced a different search tree. For example, if we had added neighbors in numeric order instead of reverse numeric order, we would have explored 5 before 3 and eventually reached 3 through
1 -> 5 -> 7 -> 3.
Starting from a different vertex in the same graph would produce a different search tree - one that contains the shortest path from that vertex to every other vertex in the search tree.
Because-depth first search relies on a stack, it is often implemented using recursion instead of an explicit stack. Below is the pseudocode for a recursive implementation of depth-first search. It produces the same search tree as the iterative version, but it does so by implicitly using the call stack to keep track of which vertex to explore next.
StartDFS(graph, start):
Map parentMap
Set visitedSet
DFS(graph, start, visitedMap, parentMap)
DFS(graph, vertex, visitedSet, parentMap):
if visitedSet.contains(vertex):
return
visitedSet.insert(vertex)
for each neighbor of vertex:
if not visitedSet.contains(neighbor):
parentMap[neighbor] = vertex
DFS(graph, neighbor, visitedSet, parentMap)
Use the interactive below to explore both implementations of depth-first search.
Activity 34.7.2. Depth-First Search.
The animation will load a random graph and start a depth-first search using the iterative algorithm from vertex 0. Step through the animation. As you do so, note how the
Known and Parent tables are updated.
Once it is done, switch to
Recursive, enter 0 as the Start Vertex in the input field and click Run DFS to see the recursive version of depth-first search produce the same search tree.
Use
New Graph button to generate a new random graph. (You may need to fast forward to the end before being able to create a new graph.
Instructions.
When the
> button is highlighted, an animation is prepared to run. Use the Step button to step through the animation one step at a time.
When no animation is in progress, you can use the data controls to start a new animation.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
-
Core Controls.
-
<<: Skip to the beginning of the animation. -
<: Step backwards one step in the animation. -
>: Step forward one step in the animation. -
>>: Skip to the end of the animation. -
Auto Step Speed Set to anything other than off to automatically step through the animation at the selected speed.
-
Zoom Set the zoom level. You can also use Ctrl + Mouse Wheel to zoom in and out.
-
-
Graph Controls.
-
New Graph Randomly generate a new graph with the same settings.
-
Directed Graph Randomly generate a new directed graph.
-
Undirected Graph Randomly generate a new undirected graph.
-
Small Graph Randomly generate a graph with 8 vertices.
-
Large Graph Randomly generate a graph with 19 vertices.
-
Logical Representation Display current graph’s logical representation.
-
Adjacency List Representation Display current graph’s adjacency list representation.
-
Adjacency Matrix Representation Display current graph’s adjacency matrix representation.
-
Checkpoint 34.7.1.
Put the following steps in the correct order to implement depth-first search:
Checkpoint 34.7.2.
Which are true statements about depth first search?
- It is naturally recursive.
- It will change its mind about how to reach certain vertices multiple times during the search.
- It produces the shortest paths possible on the search tree.
- It produces a search tree that uses every edge in the original graph.
You have attempted of activities on this page.
