SUBJECT MATERIAL, EBOOKS, IMPORTANT QUESTION , ASSIGNMENT QUESTION, OLD QUESTION PAPER

Friday, 15 July 2022

Depth-first search (DFS) in artificial intelligence

What is DFS Algorithm (Depth-First Search)? Depth-first search (DFS) is an algorithm for searching a graph or tree data structure. DFS is a... thumbnail 1 summary

What is DFS Algorithm (Depth-First Search)?

  • Depth-first search (DFS) is an algorithm for searching a graph or tree data structure.
  • DFS is also an important type of uniformed search.
  • DFS visits all the vertices in the graph.
  • This type of algorithm always chooses to go deeper into the graph.
  • After DFS visited all the reachable vertices from a particular sources vertices it chooses one of the remaining undiscovered vertices and continues the search.
  • DFS reminds the space limitation of breath first search by always generating next a child of the deepest unexpanded nodded.
  • The data structure stack or last in first out (LIFO) is used for DFS.

Why do we need DFS Algorithm?

There are numerous reasons to utilize the DFS Algorithm to use as searching for your dataset. Some of the most vital aspects that make this algorithm your first choice are:

  • Depth First Search is commonly used when you need to search the entire tree. 
  • It's easier to implement (using recursion) than BFS, and requires less state: While BFS requires you store the entire 'frontier', DFS only requires you store the list of parent nodes of the current element.

The architecture of DFS algorithm


  • The above image clearly explains the DFS Algorithm. 
  • First, the searching starts in the root node A and then goes to the branch where node B is present (lexicographical order). 
  • Then it goes do node D because of DFS and from D there is the only node to traverse i.e. node H. 
  • But after node H  does not have any child nodes so we retrace the path in which we traversed earlier and again reach node B but this time we traverse through in the untraced path a traverse through node E. 
  • There are two branches at node E but let’s traverse node I (lexicographical order) and then retrace the path as we have no further nodes after E to traverse. 
  • Then we traverse node J as it is the untraced branch and then again find we are at the end and retrace the path and reach node B and then we will traverse the untraced branch i.e. through node C and repeat the same process.

 Algorithm of DFS:

  • Step 1: PUSH the starting node into the stack.
  • Step 2: If the stack is empty then stop and return failure.
  • Step 3: If the top node of the stack is the goal node, then stop and return success.
  • Step 4: Else POP the top node from the stack and process it. Find all its neighbours that are in ready state and PUSH them into the stack in any order.
  • Step 5: Go to step 3.
  • Step 6: Exit. Exit.

Depth-First Search – Example

 

 Implementation:

  


  • Initial State – no nodes are printed and stack contains root node
  • Iteration 1 – Node A popped out and printed. Its children Node C and B are put on the stack.
  • Iteration 2 – Node B is printed and we go on to visit its children. Node B’s children Node E and Node D are pushed on to the stack
  • Iteration 4 – Current top of the stack Node D popped out and printed. Since it is a child node no other node to visit.
  • Iteration 5- The current top of the stack is Node E. Node E is popped out and printed. Since node E is leaf node, no more node to visit and we continue to the next node
  • Iteration 6 – Now Node is on top of the stack. It is popped and printed. Since it is not a child node, we push its children 9In this case we have only one child) pushed on to the stack.
  • Iteration 7 – We pop the current top of stack Node F and print it. Since it is a leaf node no more nodes to push..

Real Life Applications Of Depth-First Search Algorithm

  • For finding the strongly connected components of the graph
  • For finding the path
  • To test if the graph is bipartite
  • For detecting cycles in a graph
  • Topological Sorting
  • Solving the puzzle with only one solution.
  • Network Analysis
  • Mapping Routes
  • Scheduling a problem

 Advantages of Breadth-first search:

  • The memory requirement is Linear WRT Nodes.
  • Less time and space complexity rather than BFS.
  • The solution can be found out without much more search.

Disadvantages of Breadth-first search are:

  • Not Guaranteed that it will give you a solution.
  • Cut-off depth is smaller so time complexity is more.
  • Determination of depth until the search has proceeded.

Performance Measurement:

  • Completeness: DFS search algorithm is complete within finite state space as it will expand every node within a limited search tree.
  • Time Complexity: Time complexity of DFS will be equivalent to the node traversed by the algorithm. It is given by: T(n)= 1+ n2+ n3 +.........+ nm=O(nm)
    • Where, m= maximum depth of any node and this can be much larger than d (Shallowest solution depth)
  • Space Complexity: DFS algorithm needs to store only single path from the root node, hence space complexity of DFS is equivalent to the size of the fringe set, which is O(bm). 
  • Optimal: DFS search algorithm is non-optimal, as it may generate a large number of steps or high cost to reach to the goal node.