Depth First Search

Explanation

- Depth First Search (DFS) is a searching algorithm used in graph or tree data structures. It starts from a given node and explores as far as possible along each branch before backtracking. DFS is implemented using recursion or a stack.

-

• Steps:

  • Start from a node (typically the root node or any arbitrary node).
  • Mark the node as visited.
  • Visit its adjacent nodes that have not been visited yet.
  • This process continues recursively or using a stack, visiting each node until all nodes are explored.
  • If a node has already been visited, it is not revisited.

• Time Complexity:

  • For a graph with V vertices and E edges, the time complexity of DFS is O(V + E).