Depth First Search (DFS)

Last updated on September 4th, 2023 at 09:39 pm

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.

Advantages of Depth First Search

1. Depth-first search on a binary tree generally requires less memory than breadth-first search.
2. It can be easily implemented with recursion.

Disadvantages of Depth First Search

1. A DFS doesn’t find the shortest path to a node, while breadth-first search does.

Time Complexity of Depth First Search

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(V²) for adjacency matrix representation.

Applications of Depth First Search

1. Topological sorting
2. Finding strongly connected components
3. Find articulation points (cut vertices) of the graph
4. Solving puzzles such as mazes

Related:

Want to Contribute:-

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