DFS (Graph/Tree)

Depth first Search or DFS is a way to search recursively into the child nodes of a tree or graph rather than traversing across the breadth or siblings

Complexity: O(number of nodes in the graph) or O(V+E)

Non recursive Method:

Using a stack

Recursive Method:

Points to Note:

• DFS vs Backtracking : In a DFS , we flag/do not visit the vertices we have already visited whereas in backtracking we do not flag the vertices we have already visited that leads to exponential complexity

Applications:

• Finding loops /Cycles in a graph