.png?type=webp)
Depth First Search (DFS) Algorithm in Python
11 December, 2022
11
11
0
Contributors
Overview
Two algorithms are often used for graph traversal. These algorithms are depth-first search (DFS) and breadth-first search (BFS). DFS is like solving a MAZE. We'll continue walking through the maze's path until we reach a dead end.
The purpose of this tutorial is to provide an overview of depth-first search (DFS), its implementation in Python, and lastly the time & space complexity.
What is Depth First Search?
In DFS, we continue to traverse downwards through linked nodes until we reach the end. We then retrace our steps to check which connected nodes we haven’t visited and repeat the process.
We can see from the image below that we are trying to find a way out of the maze. Therefore, we walk deep into the maze, discovering various paths. When we reach the end, we backtrack until we find another path that we haven’t walked yet, and repeat the process
Finding an end point in the Maze using DFS.
Algorithm of DFS
To implement DFS, we use the Stack data structure to keep track of visited nodes. We begin with the root as the first element in the stack, then pop it and add all the related nodes of the popped node to the stack. We repeated the process until the stack became empty.
Every time we reach a new node, we will take the following steps:
1.
We add the node to the top of the stack.
2.
Marked it as visited.
3.
We check if this node has any adjacent nodes:
If it has adjacent nodes, check to make sure they have not been visited already, and then visit them.
We remove it from the stack if it has no adjacent nodes.
With every node added to the stack, we repeat the above steps or recursively visit each node until we reach a dead end.
Implementation of DFS
Below is the code for DFS in Python.
This results in:
Following is the Depth-first search: [0, 2, 1, 3, 4]
Time & Space Complexity
Time:
For directed graph: O(V+|E|), where V is the number of vertices and E is the number of edges.
For undirected graph: O(V+2|E|).
Space:
O(V), where V is the number of vertices.
Applications of DFS
•
Cycle Detection in graphs, Scheduling Problems, and Solving Puzzles with just one solution, such as a maze or a Sudoku puzzle, all use depth-first search.
•
Other uses involve Network Analysis, such as detecting if a graph is bipartite.
•
Depth-first searches are used in route mapping, scheduling, and finding spanning trees.
Wrap Up
In this tutorial, we take a look at DFS using Python. We have taken a look at the algorithm of DFS, and time complexity in the case of a directed and undirected graph. In short, in DFS, we continue to traverse downwards through linked nodes until we reach the end. To implement DFS, we use the stack data structure to keep track of visited nodes.
Follow me on Twitter (@triposat).
Thanks 😊
python
graphs
develevate
datastructure
dfs