DFS is the alternative to BFS, used to search data from a graph. The factor that differentiates DFS from BFS is that after starting from the root vertex, the algorithm goes down as far as possible in each of the unique single paths one by one. For each path, once it has successfully reached the ultimate depth, it flags all the vertices associated with that path as visited. After completing the path, the algorithm backtracks. If it can find another path from the root node that has yet to be visited, the algorithm repeats the previous process. The algorithm keeps on moving in the new branch until all the branches have been visited. 

Note that a graph may have a cyclic method. As mentioned, we use a Boolean flag to keep track of the vertices that have been processed to avoid iterating in cycles.

To implement DFS, we will use a stack data structure, which was discussed in detail in Chapter 2, Data Structures Used in Algorithms. Remember that stack is based on the Last In, First Out (LIFO) principle. This contrasts with a queue, which was used for BFS, which works on the First In, First Out (FIFO) principal.

The following code is used for DFS:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

Let's again use the following code to test the dfs function defined previously:

graph={ 'Amin' : {'Wasim', 'Nick', 'Mike'},
         'Wasim' : {'Imran', 'Amin'}, 
         'Imran' : {'Wasim','Faras'}, 
         'Faras' : {'Imran'},
         'Mike'  :{'Amin'}, 
         'Nick'  :{'Amin'}}

If we run this algorithm, the output will look like the following:

Let's look at the exhaustive traversal pattern of this graph using the DFS methodology:

1. The iteration starts from the top node, Amin.
2. Then, it moves to level two, Wasim. From there, it moves toward the lower levels until it reaches the end, which is the Imran and Fares nodes.
3. After completing the first full branch, it backtracks and then goes to level two to visit Nick and Mike.

The traversal pattern is shown in the following figure:

Let's now look at a case study, which explains how the concepts we have discussed so far in this chapter can be used to solve a real-world problem.