Definition of DFS Algorithm in Python
DFS algorithm in python or in general is used for searching and traversing data structure. DFS algorithm uses the idea of backtracking, in which one node is selected as the root node and it starts traversing them one by one. DFS algorithm is used to perform the searching and traversing for the data structure like tree and graph. while doing the DFS algorithm, it first chooses the left node before the right node and starts traversing them one by one. Once the particular node is travers or visited, it will not visit them again until the searching elements are found out, DFS in general stands for depth-first search, it will always first visit the left node followed by the right node associating with them. In Python, we can easily implement it by the use of sets and dictionaries, and make use of recursion also to make this work. In the coming section of the tutorial, we will see how to implement a depth-first search in Python, for a better understanding of the algorithm for beginners.
Syntax:
As we know it is an algorithm that does not have any specific implementation anyone can write their own logic to implement this. But we will have closer look at the data structure that we can use in Python to implement this algorithm efficiently let’s get started to see below.
dictionary = {
'value 1' : ['left', 'right'],
'value 2' : ['left', 'right],
'value 3' : ['left or right'],
'value 4' : [may be blank]
}As you can see in the above syntax we are creating a dictionary object here to represent the tree structure, and the value is treated here as the node after that, we can assign it a value that will be either left or right branch for that node. Let’s taken a simple practice syntax to understand this better see below;
Example:
demo = {
'1' : ['2','3'],
'2' : ['4', '5'],
'3' : ['6'],
'5' : []
}It is pretty easy to create and represent our data using a dictionary data structure. In the coming section, we will see a more detailed explanation of this algorithm in python and a step to follow to implement this.
How does the DFS Algorithm work in Python?
As of now we already know that DFS stands for depth-first search algorithm used for traversing and searching the particular element in the tree or graph data structure. The working of the depth-first search is easy to understand and we can implement the logic for it using recursion. In this section, we will first see the algorithm which will help us to understand it and also give us a detailed idea to write the code accordingly for this. Let’s get started to see below;
Depth first search (DFS) Algorithm:
- Start of the algorithm.
- First, it will pick any node from the data structure, and make it a root node.
- If the node is unvisited, it will mark it a visit and perform recursion on all of its adjacent nodes.
- It will repeat the above steps until it visits all of the nodes once or the element for which searching is found.
- End
- Exit.
Below see the reference of the flow chart for DFS algorithm in Python or in general, which will give more understanding for beginners see below;
Output:
Now we will take one simple graph structure to understand the internal working of this in detail, let’s get started to make this simpler to understand see below;
Picture:
In the above picture, we have a simple graph that we will go to traverse using the depth first search algorithm in Python, also we will understand how it starts working.
- First, it will start traversing from any element and make it a root node. In our case, ‘1’ is the root node here and it has left and right branches as well.
- As we are already aware the dfs algorithm starts traversing the element from the left branch and then the associated right branch.
- So in our case, we have ‘2’ and ‘9’ and it is left and right child we can say. And these nodes are further associated with other nodes and so on.
- So first it will go to ‘1, 2’ then it will start traversing the left node for ‘2’ in our case we have only one that is ‘3’, and the same for ‘3’ we have ‘4’ as the only left node associated with it.
- Once all the left node is being traversed then it will mark them visited and never visit them again.
- Now it will start visiting the right node, for example in our case we have ‘8’, ’10’, and others as well.
- t will traverse all of them once and at the end we have the path of traversing we can say like:
Example:
1, 2, 3, 4, 5, 6, 7, 8,9, 10
Example of DFS Algorithm in Python
In this example we are implementing the DFS algorithm in Python with the help of set and dictionary, you can provide any data here and find out the traversing path for it.
print("Demo to implement the DFS in Python by the help of Dictionary and Set data structure")
print("******** START **********************")
myGraph = {
'1' : ['2','3'],
'2' : ['5', '6'],
'3' : ['9', '10'],
'5' : ['10', '15'],
'6' : ['12', '18'],
'10' : [],
'15' : [],
'12' : [],
'18' : [],
'9' : [],
'10' : []
}
eleVisited = set()
def dfsImplementation(eleVisited, myGraph, myNode):
if myNode not in eleVisited:
print (myNode)
eleVisited.add(myNode)
for neighbour in myGraph[myNode]:
dfsImplementation(eleVisited, myGraph, neighbour)
dfsImplementation(eleVisited, myGraph, '1')Output:
Conclusion
As we have discussed it is used to traverse the grape and tree data structure, we can make use of it because it just visits one particular element once, select element as root node, etc. Also easy to handle and readable by the developers as well.
Recommended Articles
We hope that this EDUCBA information on “DFS Algorithm in Python” was beneficial to you. You can view EDUCBA’s recommended articles for more information.
