Depth First Search (DFS) Traversal

less than 1 minute read

Depth First Search (DFS)

  • Traverse all vertices in a “graph”;
  • Traverse all paths between any two vertices in a “graph”.

Time Complexity: $$ O(V+E) $$

  • 𝑉 represents the number of vertices, and
  • 𝐸 represents the number of edges.
  • We need to check every vertex and traverse through every edge in the graph.

Space Complexity: $𝑂(𝑉^2)$

  • created stack or the recursive call stack can store up to V⋅V vertices
  • worst case - each vertex has edges connecting to all other vertices.

Traversing all Vertices

Traversing all paths between two vertices

With Stack

Recursion

Memory Complexity

For a tree like structure, for the purpose of understanding

For a balanced tree with n nodes, there will n/2 leaf nodes due to which the memory complexity of BFS will on O(n)

For DFS, the max memory will the height of the tree which in logN, and that is why the memory complexity is O(logN)

You may also enjoy