java - Iterative Topological search (DFS) -

how can iterative dfs topological sort accomplished on directed acyclic graph?

here vertex

class vertex {   list<vertex> adj = new arraylist<>();   char val;    vertex(char val) {this.val = val;} } 

a recursive solution straightforward using set mark visited nodes , stack order vertices:

list<vertex> sortrecursive(list<vertex> vertices) {   deque<vertex> stack = new arraydeque<>();   set<vertex> visited = new hashset<>();   (vertex vertex : vertices) {     if (visited.contains(vertex)) continue;     sortrecursivehelper(stack, visited, vertex);   }   list<vertex> output = new arraylist<>();   while (!stack.isempty()) output.add(stack.removefirst());   return output; }  void sortrecursivehelper(deque<vertex> stack, set<vertex> visited, vertex vertex) {   visited.add(vertex);   (vertex vv : vertex.adj) {     if (visited.contains(vv)) continue;     sortrecursivehelper(stack, visited, vv);   }   stack.addfirst(vertex); } 

this driver:

vertex = new vertex('a'); vertex b = new vertex('b'); vertex c = new vertex('c'); vertex d = new vertex('d'); vertex e = new vertex('e'); vertex f = new vertex('f'); vertex g = new vertex('g');   a.adj.add(c); b.adj.add(c); b.adj.add(e); c.adj.add(d); d.adj.add(f); e.adj.add(f); f.adj.add(g);  list<vertex> output = sortrecursive(arrays.aslist(d, a, e, g, f, b, c)); system.out.println(output); 

you can keep stack of active vertices , index of first child hasn't been processed yet simulate recursion:

while stack.non_empty()     if stack.top().second == graph[stack.top().first].size:         // pop vertex here, add answer list         sorted_order.add(stack.top().first)         stack.pop_back()     else:         // next child , move increase index         // points unprocessed child         next_child = graph[stack.top().first][stack().top().second]         stack.top().second += 1         // if need go child, push         // stack instead of making recursive call         if not next_child visited:             mark next_child visited             stack.push(pair(next_child, 0))