The Depth First Search algorithm traverses the graph and explores each adjacent node before backtracking and moving to the next node. It utilizes the stack data structure. Remember, the stack uses the last-in-first-out (LIFO) approach. We push items onto the stack and pop items from the top of the stack. We’ll keep track of the stack and we’ll show the vertices in the order of which they were discovered.

We’ll begin our traversal at vertex A. Vertex A has been discovered, so it’s added to the discovery list. Vertex A is also pushed onto the stack and is marked as visited.

Vertex A is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex A. Vertex A is connected to the unvisited nodes B and G. The DFS algorithm pushes the next node onto the stack, which is B in this case since it comes next alphabetically. Vertex B is also added to the discovery list and is marked as visited.

Vertex B is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex B. Vertex B is connected to the unvisited nodes C and G. The DFS algorithm pushes the next node onto the stack, which is C in this case since it comes next alphabetically. Vertex C is also added to the discovery list and is marked as visited.

Vertex C is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex C. Vertex C is connected to the unvisited node E. The DFS algorithm pushes E onto the stack. Vertex E is also added to the discovery list and is marked as visited.

Vertex E is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex E. Vertex E is connected to the unvisited nodes G, J, and K. The DFS algorithm pushes G onto the stack. Vertex G is also added to the discovery list and is marked as visited.

Vertex G is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex G. Vertex G is connected to the unvisited node J. The DFS algorithm pushes J onto the stack. Vertex J is also added to the discovery list and is marked as visited.

Vertex J is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex J. Vertex J is connected to the unvisited nodes D and F. The DFS algorithm pushes D onto the stack. Vertex D is also added to the discovery list and is marked as visited.

Vertex D is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex D. Vertex D is connected to the unvisited nodes F and K. The DFS algorithm pushes F onto the stack. Vertex F is also added to the discovery list and is marked as visited.

Vertex F is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex F. Vertex F is connected to the unvisited node K. The DFS algorithm pushes K onto the stack. Vertex K is also added to the discovery list and is marked as visited.

At this point all nodes have been discovered. Vertex K is at the top of the stack. Since there are no other unvisited nodes that can be reached from vertex K, it’s popped from the top of the stack. The algorithm backtracks to vertex F since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex F, so it’s popped from the top of the stack. The algorithm backtracks to vertex D since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex D, so it’s popped from the top of the stack. The algorithm backtracks to vertex J since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex J, so it’s popped from the top of the stack. The algorithm backtracks to vertex G since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex G, so it’s popped from the top of the stack. The algorithm backtracks to vertex E since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex E, so it’s popped from the top of the stack. The algorithm backtracks to vertex C since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex C, so it’s popped from the top of the stack. The algorithm backtracks to vertex B since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex B, so it’s popped from the top of the stack. The algorithm backtracks to vertex A since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex A, so it’s popped from the top of the stack. The algorithm attempts to backtrack, but the stack is empty. This signals the DFS algorithm that the traversal is complete.

This was a good example of how the DFS algorithm discovers all vertices and backtracks at the end. Let’s look at another quick example where the DFS algorithm backtracks throughout the traversal.

The sample graph that we’ll use is like the previous one, but with fewer edges.

We’ll start the DFS algorithm at vertex A. Vertex A has been discovered, so it’s added to the discovery list. Vertex A is also pushed onto the stack and is marked as visited.

Vertex A is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex A. Vertex A is connected to the unvisited nodes B and G. The DFS algorithm pushes the next node onto the stack, which is B in this case since it comes next alphabetically. Vertex B is also added to the discovery list and is marked as visited.

Vertex B is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex B. Vertex B is connected to the unvisited nodes C and G. The DFS algorithm pushes the next node onto the stack, which is C in this case since it comes next alphabetically. Vertex C is also added to the discovery list and is marked as visited.

There are no other unvisited nodes that can be reached from vertex C, so it’s popped from the top of the stack. The algorithm backtracks to vertex B since it’s on top of the stack now.

Vertex B is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex B. Vertex B is connected to the unvisited node G. The DFS algorithm pushes the next node onto the stack, which is G in this case since it comes next alphabetically. Vertex G is also added to the discovery list and is marked as visited.

Vertex G is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex G. Vertex G is connected to the unvisited node E. The DFS algorithm pushes E onto the stack. Vertex E is also added to the discovery list and is marked as visited.

Vertex E is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex E. Vertex E is connected to the unvisited nodes J and K. The DFS algorithm pushes J onto the stack. Vertex J is also added to the discovery list and is marked as visited.

Vertex J is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex J. Vertex J is connected to the unvisited nodes D and F. The DFS algorithm pushes D onto the stack. Vertex D is also added to the discovery list and is marked as visited.

Vertex D is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex D. Vertex J is connected to the unvisited node K. The DFS algorithm pushes K onto the stack. Vertex K is also added to the discovery list and is marked as visited.

There are no other unvisited nodes that can be reached from vertex K, so it’s popped from the top of the stack. The algorithm backtracks to vertex D since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex D, so it’s popped from the top of the stack. The algorithm backtracks to vertex J since it’s on top of the stack now.

Vertex J is currently on top of the stack. The algorithm checks all the unvisited nodes from vertex J. Vertex J is connected to the unvisited node F. The DFS algorithm pushes F onto the stack. Vertex F is also added to the discovery list and is marked as visited.

There are no other unvisited nodes that can be reached from vertex F, so it’s popped from the top of the stack. The algorithm backtracks to vertex J since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex J, so it’s popped from the top of the stack. The algorithm backtracks to vertex E since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex E, so it’s popped from the top of the stack. The algorithm backtracks to vertex G since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex G, so it’s popped from the top of the stack. The algorithm backtracks to vertex B since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex B, so it’s popped from the top of the stack. The algorithm backtracks to vertex A since it’s on top of the stack now.

There are no other unvisited nodes that can be reached from vertex A, so it’s popped from the top of the stack. The algorithm attempts to backtrack, but the stack is empty. This signals the DFS algorithm that the traversal is complete.

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Algorithm and many more.