Depth First Search🎃
Depth-first search is a graph algorithm used in topological sorting, scheduling problems, cycle detection in graphs, and solving puzzles with only one solution, such as a maze or a sudoku puzzle.
Time complexity
The time complexity for the depth-first search is O(V+E). Where v is the number of vertices and e number of edges.
Explanation
Depth-first search is almost the same algorithm as breadth-first search and even both algorithms have the same time complexity, the only difference between these two is that breadth-first search algorithms check nodes/vertices level-wise and the depth-first search goes directly into the depth of the graph.
In depth-first search, there are also two main operations happing
- checking all the vertices/nodes in the graph
- checking all the edges of that node
- so thus O(V+E) is the time complexity of this graph.
Ps: in breadth-first search, I have already written a huge explanation about the time complexity of that graph and the same can be applied here as well.
In the below coding example I have used an undirected graph, while as in breadth-first search algorithm I have used the directed graph as an example. But the graph coordinates are the same in both examples.
