Depth First Search (DFS)

Here, We will discuss about Depth First Search (DFS), their algorithms and also explain advantages, disadvantages, time complexity and their applications.

Graph Traversals

Graph traversal means visiting every vertex and edge exactly once in a well-defined order.

During a traversal, it is important that you track which vertices have been visited. The most common way of tracking vertices is to mark them

There are two such algorithm for traversing the graphs are:

  1. Breadth First Search (BFS)
  2. Depth First Search (DFS)

What is Depth First Search(DFS)?

Depth First Search (DFS) is a recursive algorithm that uses the idea of backtracking. It works similar to preorder traversal of the tree.

DFS is better choice if the solution is at maximum depth.

This algorithm is a similar to the standard algorithm for traversing binary trees. It uses stack.

Depth First Search(DFS) Algorithm

DFS works on idea of Backtracking. It first fully explores one subtree before returning to the current node and then exploring the other subtree.

In other words, DFS involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking.

It can be implemented using stack.

depth first search - graph algorithm
  1. Depth-first search on a binary tree generally requires less memory than breadth-first search.
  2. It can be easily implemented with recursion.
  1. A DFS doesn’t find the shortest path to a node, while breadth-first search does.

Time Complexity of Breadth First Search (BFS) is O(V+E) where V is the number of nodes and E is the number of edges.

If we use adjacency list for representing graphs, then Time complexity is O(V2) for adjacency matrix representation.

  1. Topological sorting
  2. Finding strongly connected components
  3. Find articulation points (cut vertices) of the graph
  4. Solving puzzles such as mazes
Spanning forest, connected components, paths, cyclesYesYes
Shortest pathsYes
Minimal use of memory spaceYes

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 See your articles on the main page and help other coders.😎

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top