Implementing Depth First Search with Python

Introduction

Like BFS (Breadth First Search), Depth First Search or DFS is also an uninformed search technique that is applied on Graphs and Trees to search a specific node item or the shortest path of that node (In Artificial Intelligence).

In this tutorial, we will implement Depth First Search Algorithm in Python Language. Here, we will apply this search technique to graphs and trees both to understand the fundamentals more deeply. So before we start writing our code, let's get a brief knowledge of how actually DFS algorithm works through an example.

👉Visit Also: Implementing Breadth First Search with Python

How DFS (Depth First Search) works?

Let's try to understand how the BFS algorithm does work through diagrams (see below). To know it better, we will use a Tree here.

BFS starts traverse from the root node (for the case of trees only; for graphs, it can be any node chosen by the user) and then the connecting deepest child nodes. In each traversal, it stored the value of the node in a Stack. Since Stack works in LIFO (Last in first out) style, it fetches the first present node item from there and tries to find if there are any successor nodes connected with that parent node. If yes, then the algorithm traverse and stores the node item into the stack in the same way. This cycle goes on until the algorithm finds the desired node item and returns the shortest path of that node from the root or starting node.

Sometimes DFS refers to incomplete because there is a possibility of not getting our desired result (It happens when a graph has a loop or a tree has the depth of infinite level).  

Let's try to understand the logic of traversal through the below diagrams. Here, we have a single Tree having two levels (or depth) and six nodes with six data items.

Traverse A

Traverse C

Traverse F

Traverse B

Traverse E

Traverse D

I hope you guys got an idea of how DFS works actually. Here, if we try to find the optimal path between the root node 'A' and node 'E', it would be "A-B-E". This is how Breadth First Search is used to find the optimal path between two nodes (In Artificial Intelligence).

The Program

The below program will work for both Graphs and Trees (But we are taking the example of the tree here). There, we declared an extra set variable ('visited') to track if the present node is visited already or not.

It will be very helpful when a single node is getting multiple paths to reach from different nodes (In the case of Graphs, see the image above).

# A Python Program to Perform Depth First Search 

# The given tree
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

# Python set stores only identical value
visited = set()
stack = []

def DFS(graph, visited, node):
    # Adding the first node
    visited.add(node)
    stack.append(node)
    
    # Iterate through each item of the stack
    while stack:
        poppedItem = stack.pop()
        print(poppedItem, end=" ")

        # Iterate through each item of the list value of each key of the
        # graph dictionary
        for neighbor in graph[poppedItem]:
            if neighbor not in  visited:
                visited.add(neighbor)
                stack.append(neighbor)
    print("\n")

if __name__ == "__main__":
    # Calling the DFS function
    DFS(graph, visited, 'A')

Output

A C F B E D

Complexity Analysis

In Data Structure, the complexity will stand like the following.

Time Complexity: O(V+E) where V is the number of vertices or nodes, and E is the number of edges.

Space Complexity: O(V)

In Artificial Intelligence, the time complexity stands like this,

Time Complexity: O(b^d) where b is the branch factor (max. child node of a parent node), and d is the depth. Let's understand it better.

If I take the above Tree example, the depth of the Tree is 2 and a single node have a maximum of 2 child node which is the branch factor.

So, if I try to find the node 'E', the time complexity would be O(2^2) = O(4) [where, b=2, d=2]. It means, The program will take a maximum of 4 searches to find node 'E'.

Summary

In this tutorial, our topic of discussion was the Depth First Search algorithm, how it works, and the implementation of the algorithm using Python Programming. We made a single program for both Graphs and Trees to work with.

In closing, we discussed the time and space complexity of the algorithms. I hope now you can create a discussion on the Depth First Search algorithm easily.

Task for you

Try to traverse the graph example using the same python program and tell me what you get. 

If you have any doubts related to this topic, leave your message in the comment section. You will get a reply soon.

Thanks for reading!

PySeek