Everything About Depth-First Search (DFS) Algorithm In Python

As a programmer, have you ever heard about the Depth-first search algorithm? Did you ever work on programs related to the DFS algorithm? If not, you will come to know everything about a DFS algorithm clearly in this article. I have chosen this topic, especially for those who are new to python and still are in their learning stage. So, I hope you will read this article till the end so that you will gain complete knowledge about the DFS Algorithm. DFS can be sometimes difficult, then if you need guiding hands with your DFS algorithm homework? Ask our expert to assist you with your python programming assignments.

In order to know how the Depth-first search algorithm works with the Python programming language, first you have to know the clear definition of this DFS algorithm. So, let us first look at the basic definition and working of the DFS algorithm.

In general, while searching or traversing a tree or graph in data structures, this algorithm is used. The algorithm starts with selecting some arbitrary node at the root node and later it explores as far as possible along each branch before backtracking. A stack data structure is used by this algorithm for the traversal of graphs. You can use more than one DFS traversal algorithm in a graph.

You can use recursion and data structures like dictionaries and sets to implement the DFS algorithm easily. Suppose, you are given a graph with two vertices u and v, you can find path between them using the DFS algorithm. It is also used to perform topological sorting that is used to schedule jobs from given dependencies among jobs. You can also find strongly connected components of a graph using this algorithm.

There are few steps involved in the working of the DFS algorithm. The following are the steps used by the DFS algorithm:

1. First, you need to put any one of the graph’s vertices on top of a stack.
2. Now, you need to take the top item of the stack and it should be added to the visited list.
3. Then, a list of that vertex’s adjacent nodes should be created.
4. The ones which aren’t in the visited list should be added to the top of the stack.
5. Repeat the 2^nd and 3^rd  steps until the stack is empty.

Now, let us know how the pseudocode of the DFS algorithm will be. The following is the pseudocode of the DFS algorithm:

DFS(G, u)

    u.visited = true

    for each v ∈ G.Adj[u]

        if v.visited == false

            DFS(G,v)

init() {

    For each u ∈ G

        u.visited = false

     For each u ∈ G

       DFS(G, u)

}

Let us look at the explaination of this pseudocode so that you can be able to understand it clearly.

When you observe the pseudocode for DFS algorithm that is shown above. You will find that it is required to run the DFS function on every node in the init() function. Did you understand why you need to do this? You need to do this because sometimes the graph will have two different disconnected parts. At that time, you need to cover every vertex and also run the DFS algorithm on every node.

Till now, you have seen the general definition and working of a Depth first Search (DFS) algorithm. Now, you will come to know about the working of DFS algorithm in the Python programming language. I am going to explain this to you clearly using various examples.

Depth-first Search (DFS) algorithm in Python

As we discussed earlier, the DFS algorithm is used for searching and traversing data structure. It is used for the same purpose in Python also. The backtracking technique  is used by the DFS algorithm where you will be able to select one node as the root node and then you can start traversing them one by one.

In python also, you will use the DFS algorithm to perform the searching and traversing for the data structure like tree and graph. According to the DFS algorithm, first you need to choose the left node before the right node and then you will start traversing the nodes one by one. If a particular node is being travers or visited once, then it will not visit them again until you will find the elements you are trying to search. DFS in general stands for depth-first search, as it is already in it’s meaning, it will always first go to the left node and then to the right node associating with them. You can easily implement the DFS algorithm in Python by the use of sets and dictionaries. You can also make use of recursion in python to make this work.

Now, let us take an example of a simple graph structure that we will go to traverse using the depth first search algorithm in Python, so that you will understand how it starts working.

Consider the below graph structure as an example:

The following are the steps to explain the DFS algorithm in Python using the above figure:

• First thing you need to do is to start traversing from any element and make it a root node.
• From the above figure, consider ‘1’ is the root node here and it also has left and right branches.
• You all know that, in the DFS algorithm, you need to start with traversing the element from the left branch and later the right branch.
• So here we can say that, the ‘2’ and ‘9’ comes under the left and right branches. These two nodes will associate with other nodes and so on.
• Now, you will start with ‘1, 2’ then you need to traverse the left node for ‘2’. In the next case, you have only one node and that is ‘3’, and it is associated with the left node, that is ‘4’.
• Once you complete traversing all the left nodes then they will be marked as visited and they won’t be visited again.

Let us take an example of a Python program to understand these steps clearly.

Example-1:

myExampleGraph = {

‘1’ : [‘2′,’3’],

‘2’ : [‘5’, ‘6’],

‘3’ : [‘9′, ’10’],

‘5’ : [’10’, ’15’],

‘6’ : [’12’, ’18’],

’10’ : [],

’15’ : [],

’12’ : [],

’18’ : [],

‘9’ : [],

’10’ : []

}

element = set()

def DFSexample(element, myExampleGraph, exampleNode):

if exampleNode not in element:

print (exampleNode)

element.add(exampleNode)

for neighbour in myExampleGraph[exampleNode]:

DFSexample(element, myExampleGraph, neighbour)

DFSexample(element, myExampleGraph, ‘1’)

After running the above program, you will get the following output:

Output:

1

2

5

10

15

3

12

18

3

9

However, DFS is considered a part of many other algorithms that resolve problems represented by graphs such as cycle searches, path finding, topological sorting, finding articulation points and strongly connected components. The reason to use this DFS algorithm is that it is simple and easy recursive implementation.

Now, we will see an example of DFS algorithm using non-recursive or iterative method.

Are you looking for Python programming Help?

Example-2:

def dfs_non_recursive(graph, source):

       if source is None or source not in graph:

           return “Invalid input”

       path = []

       stack = [source]

       while(len(stack) != 0):

           s = stack.pop()

           if s not in path:

               path.append(s)

           if s not in graph:

               #leaf node

               continue

           for neighbor in graph[s]:

               stack.append(neighbor)

       return ” “.join(path)

DFS_path = dfs_non_recursive(graph, “A”)

print(DFS_path)

The above program gives the following output:

A B E I C F J G D H

The next example is to know the implementation of DFS algorithm in Python using Dictionary:

Example-3:

from collections import defaultdict

class Exampleprogram:

def __init__(self):

self.graph = defaultdict(list)

def addEdge(self, u, v):

self.graph[u].append(v)

def DFSUtil(self, v, visited):

visited.add(v)

print(v, end=’ ‘)

for node in self.graph[v]:

if node not in visited:

self.DFSUtil(node, visited)

def DFS(self, v):

visited = set()

self.DFSUtil(v, visited)

g = Exampleprogram()

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

print(“Following is the implementation of DFS algorithm from (starting from vertex 2)”)

g.DFS(2)

Now, let us look at some of the advantages and dis-advantages of using the DFS algorithm.

The following are the Advantages of DFS Algorithm:

1. The DFS algorithm uses very less memory space for implementation. Lack of space won’t be a big problem for implementing this algorithm. This is one of the major benefits of the Depth first search( DFS ) algorithm.
2. Another important advantage is that, it takes less time period than BFS algorithm to reach at the goal node if it traverses in a right path.
3. You will get the desired solution in the very first go because it always finds a solution without examining much of search.

The following are the Disadvantages of DFS Algorithm:

1. There is a possibility of reoccurring of the states. There is no guarantee that it finds the goal node.
2. The states may also enter into infinite loops in some cases which gives us errors in the implementation.
3. Cut-off depth is also smaller in this algorithm, so time complexity will be more.

Hence, I conclude that this is the simple explaination of the Depth first search (DFS) algorithm in the Python programming language. I hope, you all got clarity about the DFS algorithm and its implementation. Check out to learn how to convert dictionary in JSON in Python