迭代拓扑搜索（DFS）

Question

如何在有向无环图上完成迭代dfs拓扑排序？

这里是一个顶点

class Vertex { 
    List<Vertex> adj = new ArrayList<>(); 
    char val; 

    Vertex(char val) {this.val = val;} 
} 

递归溶液是直接使用一组标记访问节点和堆栈命令的顶点：

List<Vertex> sortRecursive(List<Vertex> vertices) { 
    Deque<Vertex> stack = new ArrayDeque<>(); 
    Set<Vertex> visited = new HashSet<>(); 
    for (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); 
    for (Vertex vv : vertex.adj) { 
    if (visited.contains(vv)) continue; 
    sortRecursiveHelper(stack, visited, vv); 
    } 
    stack.addFirst(vertex); 
} 

这是一个驱动程序：

Vertex a = 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); 

Answer 1

您可以保留一堆活动顶点以及尚未处理的第一个子项的索引但模拟递归：

while stack.non_empty() 
    if stack.top().second == graph[stack.top().first].size: 
     // We pop the vertex here, so we add it to the answer list 
     sorted_order.add(stack.top().first) 
     stack.pop_back() 
    else: 
     // We get the next child and move increase the index 
     // so that it points to the unprocessed child 
     next_child = graph[stack.top().first][stack().top().second] 
     stack.top().second += 1 
     // If we need to go to the child, we push it to the 
     // stack instead of making a recursive call 
     if not next_child is visited: 
      mark next_child as visited 
      stack.push(pair(next_child, 0))