title: How do I add finishing times for iterative depth-first search?
body: <p>I'm trying to create <a href="http://en.wikipedia.org/wiki/Depth-first_search#Pseudocode" rel="nofollow">depth-first</a> algorithm that assigns finishing times (the time when a vertex can no longer be expanded) which are used for things like <a href="http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm" rel="nofollow">Kosaraju's algorithm</a>. I was able to create a recursive version of DFS fairly easily, but I'm having a hard time converting it to an iterative version. </p>
  
  <p>I'm using an adjacency list to represent the graph: a dict of vertices. For example, the input graph <code>{1: [0, 4], 2: [1, 5], 3: [1], 4: [1, 3], 5: [2, 4], 6: [3, 4, 7, 8], 7: [5, 6], 8: [9], 9: [6, 11], 10: [9], 11: [10]}</code> represents edges (1,0), (1,4), (2,1), (2,5), etc. The following is the implementation of an iterative DFS that uses a simple stack (LIFO), but it doesn't compute finishing times. One of the key problems I faced was that since the vertices are popped, there is no way for the algorithm to trace back its path once a vertex has been fully expanded (unlike in recursion). How do I fix this?</p>
  
  <pre class="lang-py prettyprint-override"><code>def dfs(graph, vertex, finish, explored):
      global count
  
      stack = []
      stack.append(vertex)
  
      while len(stack) != 0:
          vertex = stack.pop()
  
          if explored[vertex] == False:
              explored[vertex] = True
  
              #add all outgoing edges to stack:
              if vertex in graph:                 #check if key exists in hash -- since not all vertices have outgoing edges
                  for v in graph[vertex]:
                      stack.append(v)
  
          #this doesn't assign finishing times, it assigns the times when vertices are discovered:                                            
          #finish[count] = vertex
          #count += 1
  </code></pre>
  
  <p>N.b. there is also an outer loop that complements DFS -- though, I don't think the problem lies there:</p>
  
  <pre class="lang-py prettyprint-override"><code>#outer loop:
  for vertex in range(size, 0, -1):
      if explored[vertex] == False:
          dfs(hGraph, vertex, finish, explored)
  </code></pre>