Non-recursive depth first search algorithm

Question

I am looking for a non-recursive depth first search algorithm for a non-binary tree  Any help is very much appreciated

User · Answer

An ES6 implementation based on biziclops great answer:

_x000D_

root = {_x000D_
  text: "root",_x000D_
  children: [{_x000D_
    text: "c1",_x000D_
    children: [{_x000D_
      text: "c11"_x000D_
    }, {_x000D_
      text: "c12"_x000D_
    }]_x000D_
  }, {_x000D_
    text: "c2",_x000D_
    children: [{_x000D_
      text: "c21"_x000D_
    }, {_x000D_
      text: "c22"_x000D_
    }]_x000D_
  }, ]_x000D_
}_x000D_
_x000D_
console.log("DFS:")_x000D_
DFS(root, node => node.children, node => console.log(node.text));_x000D_
_x000D_
console.log("BFS:")_x000D_
BFS(root, node => node.children, node => console.log(node.text));_x000D_
_x000D_
function BFS(root, getChildren, visit) {_x000D_
  let nodesToVisit = [root];_x000D_
  while (nodesToVisit.length > 0) {_x000D_
    const currentNode = nodesToVisit.shift();_x000D_
    nodesToVisit = [_x000D_
      ...nodesToVisit,_x000D_
      ...(getChildren(currentNode) || []),_x000D_
    ];_x000D_
    visit(currentNode);_x000D_
  }_x000D_
}_x000D_
_x000D_
function DFS(root, getChildren, visit) {_x000D_
  let nodesToVisit = [root];_x000D_
  while (nodesToVisit.length > 0) {_x000D_
    const currentNode = nodesToVisit.shift();_x000D_
    nodesToVisit = [_x000D_
      ...(getChildren(currentNode) || []),_x000D_
      ...nodesToVisit,_x000D_
    ];_x000D_
    visit(currentNode);_x000D_
  }_x000D_
}

_x000D_

User · Answer

Suppose you want to execute a notification when each node in a graph is visited  The simple recursive implementation is   void DFSRecursive Node n  Set lt Node gt  visited      visited add n     for  Node x   neighbors of n         iterate over all neighbors     if   visited contains x           DFSRecursive x  visited               OnVisit n       callback to say node is finally visited  after all its non-visited neighbors     Ok  now you want a stack-based implementation because your example doesn t work  Complex graphs might for instance cause this to blow the stack of your program and you need to implement a non-recursive version  The biggest issue is to know when to issue a notification   The following pseudo-code works  mix of Java and C   for readability    void DFS Node root      Set lt Node gt  visited    Set lt Node gt  toNotify      nodes we want to notify    Stack lt Node gt  stack    stack add root     toNotify add root       we won t pop nodes from this until DFS is done   while   stack empty          Node current   stack pop        visited add current       for  Node x   neighbors of current           if   visited contains x             stack add x           toNotify add x                          Now issue notifications  toNotifyStack might contain duplicates  will never      happen in a tree but easily happens in a graph    Set lt Node gt  notified    while   toNotify empty        Node n   toNotify pop      if   toNotify contains n         OnVisit n       issue callback     toNotify add n           It looks complicated but the extra logic needed for issuing notifications exists because you need to notify in reverse order of visit - DFS starts at root but notifies it last  unlike BFS which is very simple to implement   For kicks  try following graph  nodes are s  t  v and w  directed edges are  s- t  s- v  t- w  v- w  and v- t  Run your own implementation of DFS and the order in which nodes should be visited must be  w  t  v  s A clumsy implementation of DFS would maybe notify t first and that indicates a bug  A recursive implementation of DFS would always reach w last

User · Answer

Just wanted to add my python implementation to the long list of solutions  This non-recursive algorithm has discovery and finished events    worklist    root node  visited   set   while worklist      node   worklist -1      if node in visited            Node is finished         worklist pop       else            Node is discovered         visited add node          for child in node children              worklist append child

User · Answer

While  use a stack  might work as the answer to contrived interview question  in reality  it s just doing explicitly what a recursive program does behind the scenes   Recursion uses the programs built-in stack  When you call a function  it pushes the arguments to the function onto the stack and when the function returns it does so by popping the program stack

User · Answer

Stack lt Node gt  stack   new Stack lt  gt     stack add root   while   stack isEmpty          Node node   stack pop        System out print node getData      quot   quot         Node right   node getRight        if  right    null            stack push right              Node left   node getLeft        if  left    null            stack push left

User · Answer

If you have pointers to parent nodes  you can do it without additional memory   def dfs root       node   root     while True          visit node          if node first child              node   node first child        walk down         else              while not node next sibling                  if node is root                      return                 node   node parent         walk up                 node   node next sibling           and right   Note that if the child nodes are stored as an array rather than through sibling pointers  the next sibling can be found as   def next sibling node       try          i      node parent child nodes index node          return node parent child nodes i 1      except  IndexError  AttributeError           return None

User · Answer

DFS   list nodes to visit    root   while  nodes to visit isn t empty       currentnode   nodes to visit take first      nodes to visit prepend  currentnode children        do something     BFS   list nodes to visit    root   while  nodes to visit isn t empty       currentnode   nodes to visit take first      nodes to visit append  currentnode children        do something     The symmetry of the two is quite cool   Update  As pointed out  take first   removes and returns the first element in the list

User · Answer

Non-recursive DFS using ES6 generators  class Node     constructor name  childNodes        this name   name      this childNodes   childNodes      this visited   false         function  dfs s      let stack         stack push s     stackLoop  while  stack length        let u   stack stack length - 1      peek     if   u visited          u visited   true     grey - visited       yield u             for  let v of u childNodes          if   v visited            stack push v           continue stackLoop                     stack pop       black - all reachable descendants were processed              It deviates from typical non-recursive DFS to easily detect when all reachable descendants of given node were processed and to maintain the current path in the list stack

User · Answer

http   www youtube com watch v zLZhSSXAwxI  Just watched this video and came out with implementation  It looks easy for me to understand  Please critique this   visited node  root  stack push root  while  stack empty     unvisited node   get unvisited adj nodes stack top       If  unvisited node  null        stack push unvisited node          visited node  unvisited node        else      stack pop

User · Answer

You can use a stack  I implemented graphs with Adjacency Matrix   void DFS int current       for int i 1  i lt N  i    visit table i  false      myStack push current       cout  lt  lt  current  lt  lt            while  myStack empty             current   myStack top            for int i 0  i lt N  i                 if AdjMatrix current  i     1                   if visit table i     false                        myStack push i                       visit table i    true                      cout  lt  lt  i  lt  lt                                          break                            else if  myStack empty                    myStack pop

User · Answer

DFS iterative in Java     DFS  Iterative private Boolean DFSIterative Node root  int target        if  root    null          return false      Stack lt Node gt   stack   new Stack lt Node gt          stack push root       while   stack size    gt  0            Node temp    stack peek            if  temp data    target              return true          if  temp left    null               stack push temp left           else if  temp right    null               stack push temp right           else              stack pop              return false

User · Answer

Pseudo-code based on  biziclop s answer    Using only basic constructs  variables  arrays  if  while and for Functions getNode id  and getChildren id  Assuming known number of nodes N        NOTE  I use array-indexing from 1  not 0    Breadth-first  S   Array N  S 1    1     root id cur   1  last   1 while cur  lt   last     id   S cur      node   getNode id      children   getChildren id       n   length children      for i   1  n         S  last i     children i      end     last   last n     cur   cur 1      visit node  end   Depth-first  S   Array N  S 1    1     root id cur   1  while cur  gt  0     id   S cur      node   getNode id      children   getChildren id       n   length children      for i   1  n            assuming children are given left-to-right         S  cur i-1     children  n-i 1                otherwise            S  cur i-1     children i       end     cur   cur n-1      visit node  end

User · Answer

Use a stack to track your nodes  Stack lt Node gt  s   s prepend tree head    while  s empty        Node n   s poll front    gets first node         do something with q       for each child of n  s prepend child

User · Answer

Using Stack  here are the steps to follow  Push the first vertex on the stack then    If possible  visit an adjacent unvisited vertex  mark it  and push it on the stack  If you can   t follow step 1  then  if possible  pop a vertex off the stack  If you can   t follow step 1 or step 2  you   re done      Here s the Java program following the above steps   public void searchDepthFirst            begin at vertex 0     vertexList 0  wasVisited   true      displayVertex 0       stack push 0       while   stack isEmpty              int adjacentVertex   getAdjacentUnvisitedVertex stack peek                if no such vertex         if  adjacentVertex    -1                stack pop              else               vertexList adjacentVertex  wasVisited   true                 Do something             stack push adjacentVertex                          stack is empty  so we re done  reset flags     for  int j   0  j  lt  nVerts  j                vertexList j  wasVisited   false

User · Answer

PreOrderTraversal is same as DFS in binary tree  You can do the same recursion  taking care of Stack as below       public void IterativePreOrder Tree root                                if  root    null                      return                  Stack s lt Tree gt    new Stack lt Tree gt                     s Push root                   while  s Count    0                                        Tree b   s Pop                        Console Write b Data                             if  b Right    null                          s Push b Right                       if  b Left    null                          s Push b Left                                      The general logic is  push a node starting from root  into the Stack  Pop   it and Print   value  Then if it has children  left and right  push them into the stack - push Right first so that you will visit Left child first after visiting node itself   When stack is empty   you will have visited all nodes in Pre-Order

User · Answer

You would use a stack that holds the nodes that were not visited yet   stack push root  while  stack isEmpty   do     node   stack pop       for each node childNodes do         stack push stack      endfor            endwhile

User · Answer

FULL example WORKING code  without stack   import java util     class Graph   private List lt List lt Integer gt  gt  adj   Graph int numOfVertices        this adj   new ArrayList lt  gt         for  int i   0  i  lt  numOfVertices    i          adj add i  new ArrayList lt  gt         void addEdge int v  int w        adj get v  add w      Add w to v s list     void DFS int v        int nodesToVisitIndex   0      List lt Integer gt  nodesToVisit   new ArrayList lt  gt         nodesToVisit add v       while  nodesToVisitIndex  lt  nodesToVisit size              Integer nextChild  nodesToVisit get nodesToVisitIndex       get the node and mark it as visited node by inc the index over the element          for  Integer s   adj get nextChild                 if   nodesToVisit contains s                     nodesToVisit add nodesToVisitIndex  s     add the node to the HEAD of the unvisited nodes list                                  System out println nextChild            void BFS int v        int nodesToVisitIndex   0      List lt Integer gt  nodesToVisit   new ArrayList lt  gt         nodesToVisit add v       while  nodesToVisitIndex  lt  nodesToVisit size              Integer nextChild  nodesToVisit get nodesToVisitIndex       get the node and mark it as visited node by inc the index over the element          for  Integer s   adj get nextChild                 if   nodesToVisit contains s                     nodesToVisit add s     add the node to the END of the unvisited node list                                  System out println nextChild            public static void main String args          Graph g   new Graph 5        g addEdge 0  1       g addEdge 0  2       g addEdge 1  2       g addEdge 2  0       g addEdge 2  3       g addEdge 3  3       g addEdge 3  1       g addEdge 3  4        System out println  Breadth First Traversal- starting from vertex 2         g BFS 2       System out println  Depth First Traversal- starting from vertex 2         g DFS 2        output  Breadth First Traversal- starting from vertex 2  2 0 3 1 4 Depth First Traversal- starting from vertex 2  2 3 4 1 0

User · Answer

Here is a link to a java program showing DFS following both reccursive and non-reccursive methods and also calculating discovery and finish time  but no edge laleling       public void DFSIterative         Reset        Stack lt Vertex gt  s   new Stack lt  gt         for  Vertex v   vertices values              if   v visited                v d     time              v visited   true              s push v               while   s isEmpty                      Vertex u   s peek                    s pop                    boolean bFinished   true                  for  Vertex w   u adj                        if   w visited                            w visited   true                          w d     time                          w p   u                          s push w                           bFinished   false                          break                                                          if  bFinished                        u f     time                      if  u p    null                          s push u p                                                       Full source here

[algorithm] Non-recursive depth first search algorithm

Examples related to algorithm

Examples related to tree