迭代拓扑搜索(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))