反復トポロジカル検索（DFS）

Question

反復dfsトポロジカルソートは、有向非循環グラフ上でどのように実行できますか？ドライバ

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); 
} 

このさ：

ここ

は

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

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

再帰溶液が訪問ノードをマークするセットを使用して容易である頂点と頂点を注文するスタックであります

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))