title: Topological sort python
body: <p>I coded a solution for DFS non-recursive, but i can't modify it to make a topological sort:</p>
  
  <pre><code>def dfs(graph,start):
      path = []
      stack = [start]    
      while stack != []: 
          v = stack.pop()
          if v not in path: path.append(v)
          for w in reversed(graph[v]): 
              if w not in path and not w in stack:
                  stack.append(w) 
      return path
  </code></pre>
  
  <p>Any ideas how to modify it?</p>
  
  <p>With the recursive version i can easy have the sorting:</p>
  
  <pre><code>def dfs_rec(graph,start,path):
      path = path + [start]
      for edge in graph[start]: 
          if edge not in path:
              path = dfs_rec(graph, edge,path)
      print start
      return path
  </code></pre>
  
  <p>Input:</p>
  
  <pre><code>&gt;&gt;&gt; graph = {
          1: [2, 3],
          2: [4, 5, 6],
          3: [4,6],
          4: [5,6],
          5: [6],
          6: []
      }
  &gt;&gt;&gt; dfs_rec(graph,1,[])
  6
  5
  4
  2
  3
  1
  [1, 2, 4, 5, 6, 3]
  &gt;&gt;&gt; dfs(graph,1)
  [1, 2, 4, 5, 6, 3]
  &gt;&gt;&gt; graph = {
          1: [3],
          3: [5,6],
          5: [4],
          4: [7],
          7: [],
          6: []
      }
  &gt;&gt;&gt; print dfs_rec(graph,1,[])
  7
  4
  5
  6
  3
  1
  [1, 3, 5, 4, 7, 6]
  &gt;&gt;&gt; print dfs(graph,1)
  [1, 3, 5, 4, 7, 6]
  </code></pre>
  
  <p>so i need to get this ordering in the non-recursive also.</p>
  
  <h2>Non-recursive solution:</h2>
  
  <p>I think that this also could be the solution, mark me if i am wrong.</p>
  
  <pre><code>def dfs(graph,start):
      path = []
      stack = [start]
      label = len(graph)
      result = {}  
      while stack != []:
          #this for loop could be done in other ways also
          for element in stack:
              if element not in result:
                  result[element] = label
                  label = label - 1
  
          v = stack.pop()
          if v not in path: path.append(v)
          for w in reversed(graph[v]): 
              if w not in path and not w in stack:
                  stack.append(w) 
  
      result = {v:k for k, v in result.items()}
      return path,result
  </code></pre>
  
  <p>Input:</p>
  
  <pre><code>graph = { 1: [3], 3:[5,6] , 5:[4] , 4:[7], 7:[],6:[]}
  print dfs(graph,1) 
  </code></pre>
  
  <p>Output:</p>
  
  <pre><code>([1, 3, 5, 4, 7, 6], {1: 7, 2: 4, 3: 5, 4: 6, 5: 3, 6: 1})
  
          1
         / 
        3
       /\
      5  6
     /
    4
   /
  7    
  </code></pre>