迭代拓撲搜索（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))