title: Python Iterative Depth First Search from table
body: <p>I have the following data table:</p>
  
  <pre><code>child_pid   parent_pid
         1        -1
         2         1
         6        -1
         7         6
         8         7
         9         8
         21       -1
         22       21
         24       -1
         25       24
         26       25
         27       26
         28       27
         29       28
         99        6
         107      99
         108      -1
         109      108
         222      109
         1000      7
         1001     1000
  </code></pre>
  
  <p>I want to write a python iterative depth-first search that generates the following result:</p>
  
  <pre><code>('final: ',
     [[u'1', u'2'],
     [u'6', u'7', u'8', u'9'],
     [u'6', u'7', u'1000', u'1001'],
     [u'6', u'99', u'107'],
     [u'21', u'22'],
     [u'24', u'25', u'26', u'27', u'28', u'29'],
     [u'108', u'109', u'222']])
  </code></pre>
  
  <p>The above output was generated using a recursive approach.  We can see that all the child/parent relationships are preserved appropriately.  </p>
  
  <p>I've utilized the following logic from another tutorial in my attempt to derive an iterative approach:</p>
  
  <pre><code>def dfs_iterative(graph, start):
      stack, path = [start], []
  
      while stack:
          vertex = stack.pop()
          if vertex in path:
              continue
          path.append(vertex)
          for neighbor in graph[vertex]:
              stack.append(neighbor)
  
      return path
  </code></pre>
  
  <p>which results in:</p>
  
  <pre><code>('final: ',
     [[u'1', u'2'],
     [u'6', u'99', u'107', u'7', u'1000', u'1001', u'8', u'9'],
     [u'21', u'22'],
     [u'24', u'25', u'26', u'27', u'28', u'29'],
     [u'108', u'109', u'222']])
  </code></pre>
  
  <p>We can see that the results are almost identical except for when a node has more than one child.  Specifically, node 6 has the following relationships:</p>
  
  <pre><code>6-&gt;7-&gt;8-&gt;9
  6-&gt;7-&gt;1000-&gt;1001
  6-&gt;99-&gt;107
  </code></pre>
  
  <p>In the recursive output above, we see that node 6 is appropriately broken out into its proper path relationships.  In my iterative attempt, all of node 6's "descendants" are grouped together into one list.  Looking for way to generate the recursive output, but with an iterative approach in python.  Thoughts?  I appreciate the help!</p>