Depth First Search(DFS)- DSA

By | September 12, 2019

Graph and Trees are two similar like Data structures with some difference, and Depth First Search is a traversing or searching algorithm that can apply to both the structures. The DFS algorithm was investigated by Charles Pierre Trémaux back in the 19th century. Here in this article, we have covered the DFS (Depth First Search) algorithm for Graph Data Structures.

What is DFS?

DFS Stands for Depth First Search and it is an algorithm used to traverse through a Graph data structure and can also be used for searching purpose.

As we know that in a Graph Data Structure, we use edges and vertices so to traverse from one vertex to another we use edges, in DFS we visit each vertex only one time, once we have visited a vertex (node) so we block all the edges pointing to it, so we do not visit the same node twice.

If we use the DFS algorithm to traverse through all nodes, here our main goal to search as deeply as possible.

We use the stack data structure along with DFS, which is used to hold all the visited node.

The DFS algorithm traversing for searching start from the head of the node and end with the last visited leaf node. In between if the algorithm leads to one of the leaf nodes, then it backtracks from that leaf node to the most recent node and tries to visit the unvisited node. In DFS we often use the recursion for backtracking.

DFS Algorithm

  • Step1: Start Traversing with the head node.
  • Step 2: Visit the adjacent node and push it into the stack.
  • Step 3: Repeat Step 2 until reach the leaf node.
  • Step 4: Once reached to the leaf node pop it from the stack.
  • Step 5: Pop all the nodes that have been push into the stack and have no further adjacent node to visit (backtracking).

DFS Properties

  • Space and time complexity of DFS vary according to its application
  • The conventional use of DFS to traverse through a given graph.
  • The Space complexity of DFS depends upon the number of vertices.
  • DFS has many real-world applications and heavily used in Artificial Intelligence.

Advantages and Disadvantages of DFS

Advantages

  • Use less memory.
  • It can find the largest distance with less time because it tries to find all the leaf nodes first.

Disadvantage

  • Does not provides an optimal solution
  • Also, visit the unwanted path.

DFS Applications

  • Topological sorting
  • Finding the bridge of a graph
  • Generating words to plot set of groups.
  • Finding bi-connectivity in the graph.

DFS Implementation 

Python

from collections import defaultdict 
class Graph: 
  def __init__(self): 
    self.graph = defaultdict(list) 
  def addEdge(self,u,v): 
    self.graph[u].append(v) 
  def DFSUtil(self, v, visited): 
    visited[v]= True
    print(v) 
    for i in self.graph[v]: 
      if visited[i] == False: 
        self.DFSUtil(i, visited) 
  def DFS(self): 
    V = len(self.graph) #total vertices 
    visited =[False]*(V) 
    for i in range(V): 
      if visited[i] == False: 
        self.DFSUtil(i, visited) 
g = Graph() # Create a graph
g.addEdge(0, 1) 
g.addEdge(0, 2) 
g.addEdge(1, 2) 
g.addEdge(2, 0) 
g.addEdge(2, 3) 
g.addEdge(3, 3) 
print("Following is Depth First Traversal")
g.DFS() 

OUTPUT:

Following is Depth First Traversal
0
1
2
3

Leave a Reply

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