Which search method takes less memory?

0 votes
1317 views
Khushi Kapoor asked 25-Nov-2017 in Technology by Khushi Kapoor

Which search method takes less memory?

1 Answer

0 votes
akriti kashyap answered 17-Jan-2018 by akriti kashyap

Search Method Holding On Less Memory!

Which search method takes less memory?

Depth-First Search is the traversal technique that occupies less space in memory. Well, this is fine if it takes less memory space but exactly it is… that is a question!

Depth First Search (DFS):

Which search method takes less memory?

It is an algorithm which is recursive in nature and uses the idea of backtracking. It involves all the possible searches that maybe exhaustive as it traverses through all the nodes and if required then it backtrack also.

Now, a new term is been tossed “Backtrack”, thus it can be explained as while traversing through the nodes, if we encounter with a node that is a child node, it steps backward from that node to find the next path that can be traversed. All the nodes would be visited on the current path, till the time every unvisited node is not been traversed, after that only can a next path be chosen.

Stating about its functionality, DFS can be implemented using stacks, which can be shown in the below code:

  • Pivot the starting node and stack the rest of the adjacent nodes in the stack
  • Pop a node from the stack to select the next node to traverse and Push all its adjacent nodes into the stack
  • Continue, repeating this until the stack is empty. However, a mark is been made if the node is been visited wherein, this function would prevent you from visiting the same node again and again and if not then may you end up in the condition of infinite loop    


Pseudocode:

DFS (G, s): //Where G is graph and s is source vertex 
      Let A be stack
      A.push(s) //Inserting s in stack
      mark A as visited.
      while (A is not empty):
          //Pop a vertex from stack to visit next
          b = A.top( )
          A.pop ( )
          //Push all the neighbors of v in stack that are not visited
        for all neighbors c of b in Graph G:
            if c is not visited :
                     A.push(c)
                    mark c as visited
DFS-recursive (G, s): 
        mark s as visited
        for all neighbors c of s in Graph G:
            if c is not visited:
                DFS-recursive (G, c)

Hope this would help you to get the info about DFS!

Cheers!

UTKARSHASINGHROUL commented 24-Apr-2019 by UTKARSHASINGHROUL
Nice answer.
       0