Graph Traversal in Python: Depth First Search (DFS)

Depth First Search (DFS) or Depth First Traversal (DFT) is another fundamental graph algorithm that similar to the previous discussed BFS or BFT. The only, minor difference is that the depth first algorithm goes into deeper level node whenever it’s possible.

For example, in the same case as BFS starting with node “A”, DFS goes to “B” and followed by “D” and “E”, “F”. Then goes to “C”. But why it scans “E” after “D” , arn’t “E” and “D” at the same level? That is because “D” has no more subnode connected. The algorithm goes back to “B” and look for subnode of “B”, that would be “E”. Note that “E” has a subnode “F”, which is also a subnode of “C”. It may be scanned twice and we need to take care of it later.

To impliment it in code, we need to find a way to ensure the “depth first” sequence. A stack with “Last-In-First-Out” principle may helpful to achieve it. As shown in illustration below: we put the first node in and pop it out, trade the “A” with “B” and “C” but to remain a left-to-right scanning we reverse it to “C” and “B”, push them into the stack. Next round we pop out “B” and trade for subnode of “B” and so on.

The graph in python is represented in the form of dictionary so that you can retrive the values using keys. In our example we insert ‘A’ to retrive ‘B’ and ‘C’.

graph={
 ‘A’:[‘B’,’C’],
 ‘B’:[‘D’,’E’],
 ‘C’:[‘F’],
 ‘D’:[],
 ‘E’:[‘F’],
 ‘F’:[]
}
graph[‘A’]
# this should gives you ['B','C']

The above code in the graph form is like this below (note that there is direction):

To compare with our previous BFS implimentation, we code the DFS in the BFS style. All the variable names and location are set the same except the “queue” structure and “stack” structure are slightly different. As we explain in the previous article, the “queue” is to ensure “First-In-First-Out” principle so that breadth search is fully finished before next level node search. A “stack” on the other hand, prefer to play with the newly inserted element so that depth first search is achieved.

def dfs(graph,node):
    
    # node is the starting position
    # graph is the graph in dictionary format
    visited=[]
    queue=[]
    
    queue.append(node)
    visited.append(node)
    
    while queue:
        s=queue.pop()
        print(s)
        for x in graph[s][::-1]:
            if x not in visited:
                visited.append(x)
                queue.append(x)

Let’s test out some examples:

graph={
    'A':['B','C'],
    'B':['D','E'],
    'C':['F'],
    'D':[],
    'E':['F'],
    'F':[]
}
dfs(graph,'A')
# this will return the sequence of A,B,D,E,F,C

And the other example:

graph={
    'A':['C','E'],
    'B':[],
    'C':['B','G'],
    'D':[],
    'E':['H'],
    'H':['D'],
    'G':[]
}
dfs(graph,'A')
# this will return the sequence of A,C,B,G,E,H,D

This link used recursive method to search depth which is simplier in coding but slightly tricky for understanding, especially when you are not familar with recursive programming. We will explain the understanding of recursive method in the future articles.

How to implement depth-first search in Python