最近我需要实现非递归DFS作为更复杂的算法的一部分，准确地说是Tarjan的算法。递归实现非常优雅，但不适合大型图形。当我实现迭代版本时，我对它最终变得如此不优雅感到震惊，我想知道我是否做错了什么。
迭代 DFS 有两种基本方法。首先，您可以将节点的所有子节点一次推送到堆栈上（似乎更常见）。或者你可以只推一个。我将专注于第一个，因为似乎每个人都是这样做的。
我对这个算法有各种各样的问题，最终我意识到要有效地做到这一点，我需要的不是 1，不是 2，而是 3 个布尔标志（我不一定意味着你需要三个显式布尔变量，你可以通过变量的特殊值间接存储信息通常是整数，但你需要以一种或另一种方式访问这 3 条信息。三面旗帜是：1）访问。这是为了防止孩子被非常多余地推到堆栈上。2）完成。防止对同一节点进行冗余处理。3）升序/降序。指示子项是否已被推到堆栈上。伪代码如下所示：
while(S)
if S.peek().done == True
S.pop()
continue
S.peek().visited = True
if S.peek().descending == True
S.peek().descending = False
for c in S.peek().children
if c.visited == False
S.push(c)
doDescendingStuff()
else
w = S.pop()
w.done = True
doAscendingStuff()
一些注意事项：1）技术上你不需要上升/下降，因为你可以看看孩子是否都完成了。但是在密集图中效率很低。
2），主要踢球者：访问/完成的事情似乎没有必要。这就是为什么（我认为）你需要它。在堆栈上访问访问之前，您无法标记访问的内容。如果这样做，则可能会以错误的顺序处理事情。例如，假设 A 链接到 B 和 C，B 链接到 D，D 链接到 C。然后从 A 开始，您将在堆栈上推送 B 和 C。从 B 开始，您将 D 推到堆栈上...然后呢？如果您在堆栈上推送内容时标记访问过的内容，则不会在此处将 C 推送到堆栈上。但这是错误的，在这个图中，C 应该从 D 访问，而不是从 A 访问（假设 A 在 C 之前访问 B）。因此，在处理访问的内容之前，您不会标记它们。但是，您将在堆栈上出现两次 C。所以你需要另一个标志来表明你已经完全完成了它，所以你不会第二次处理 C。
我不明白如何避免这一切，拥有一个完全正确的非递归 DFS，它支持缠绕和展开的操作。但本能地感觉很粗糙。有没有更好的方法？我在网上咨询过的几乎每个地方都对如何实际实现非递归DFS进行了掩饰，说它可以做到并提供一种非常基本的算法。当算法是正确的（就正确支持到同一节点的多个路径而言）时，这种情况很少见，它很少正确地支持在绕组和展开时执行操作。
我认为最优雅的基于堆栈的实现会在堆栈上而不是节点上具有子级迭代器。将迭代器视为在其子节点中存储节点和位置。
while (!S.empty)
Iterator i = S.pop()
bool found = false
Iterator temp = null
while (i.hasNext())
Node n = i.next()
if (n.visited == false)
n.visited = true
doDescendingStuff(n)
temp = n.getChildrenIterator()
break
if (!i.hasNext())
doAscendingStuff(i.getNode())
else
S.push(i)
if (temp != null)
S.push(temp)
以上可以通过将节点和位置分离到 2 个堆栈上来优化 i.t.o 存储空间。
代码无法完全模拟递归 DFS 实现发生的情况。在递归 DFS 实现中，每个节点在任何时候都只在堆栈中出现一次。
Dukeling给出的解决方案是一种迭代的方法。基本上，您一次只需在堆栈中推送一个节点，而不是一次推送所有节点。
您断言这将需要更多的存储是错误的：通过您的实现，一个节点可以在堆栈上多次出现。事实上，如果你从一个非常密集的图（所有顶点上的完整图）开始，就会发生这种情况。使用杜克林解决方案，堆栈的大小为 O（顶点数）。在您的解决方案中，它是 O（边数）。
算法 BFS（G， v）
enqueue(Q, v)
mark v as visited
while Q is not empty do
let w = front(Q)
visit(w)
dequeue(Q)
for each vertex u adjacent to w do
if u is not marked
enqueue(Q, u)
mark u as visited
算法 DFS（G， v）
push(S, v)
mark v as visited
visit(v)
while S is not empty do
let w = top(S)
pop(S)
find the first umarked vertex u that is adjacent to w
if found such vertex u
push(S, u)
mark u as visited
visit(u)
else if not found such vertex u
pop(S)
Robert Sedgewick在cpp书中的算法谈到了一个特殊的堆栈，它只保留一个项目的一个副本，而忘记了旧副本。不完全确定如何执行此操作，但它消除了堆栈中有多个项目的问题。
dr 是你不需要超过一个标志。
实际上，您可以通过显式执行编译器对运行时堆栈执行的操作，将递归 DFS 转换为迭代。该技术使用 goto s 来模拟调用和返回，但这些可以转换为更具可读性的循环。我将使用 C 语言，因为您实际上可以编译中间结果：
#include <stdio.h>
#include <stdlib.h>
#define ARITY 4
typedef struct node_s {
struct node_s *child[ARITY];
int visited_p;
} NODE;
// Recursive version.
void dfs(NODE *p) {
p->visited_p = 1;
for (int i = 0; i < ARITY; ++i)
if (p->child[i] && !p->child[i]->visited_p)
dfs(p->child[i]);
}
// Model of the compiler's stack frame.
typedef struct stack_frame_s {
int i;
NODE *p;
} STACK_FRAME;
// First iterative version.
void idfs1(NODE *p) {
// Set up the stack.
STACK_FRAME stack[100];
int i, sp = 0;
// Recursive calls will jump back here.
start:
p->visited_p = 1;
// Simplify by using a while rather than for loop.
i = 0;
while (i < ARITY) {
if (p->child[i] && !p->child[i]->visited_p) {
stack[sp].i = i; // Save params and locals to stack.
stack[sp++].p = p;
p = p->child[i]; // Update the param to its new value.
goto start; // Emulate the recursive call.
rtn: ; // Emulate the recursive return.
}
++i;
}
// Emulate restoring the previous stack frame if there is one.
if (sp) {
i = stack[--sp].i;
p = stack[sp].p;
goto rtn; // Return from previous call.
}
}
现在在代码上做一些"代数"，开始摆脱goto。
void idfs2(NODE *p) {
STACK_FRAME stack[100];
int i, sp = 0;
start:
p->visited_p = 1;
i = 0;
loop:
while (i < ARITY) {
if (p->child[i] && !p->child[i]->visited_p) {
stack[sp].i = i;
stack[sp++].p = p;
p = p->child[i];
goto start;
}
++i;
}
if (sp) {
i = stack[--sp].i + 1;
p = stack[sp].p;
goto loop;
}
}
不断变换，我们最终会在这里：
void idfs3(NODE *p) {
STACK_FRAME stack[100];
int i, sp = 0;
p->visited_p = 1;
i = 0;
for (;;) {
while (i < ARITY) {
if (p->child[i] && !p->child[i]->visited_p) {
stack[sp].i = i;
stack[sp++].p = p;
p = p->child[i];
p->visited_p = 1;
i = 0;
} else {
++i;
}
}
if (!sp) break;
i = stack[--sp].i + 1;
p = stack[sp].p;
}
}
这很好。还有一个可选的"抛光"步骤。我们可以最初在堆栈上推送根，以稍微简化外部循环：
void idfs3(NODE *p) {
STACK_FRAME stack[100];
p->visited_p = 1;
stack[0].i = 0
stack[0].p = p;
int sp = 1;
while (sp > 0) {
int i = stack[--sp].i;
p = stack[sp].p;
while (i < ARITY) {
if (p->child[i] && !p->child[i]->visited_p) {
stack[sp].i = i + 1;
stack[sp++].p = p;
p = p->child[i];
p->visited_p = 1;
i = 0;
} else {
++i;
}
}
}
}
在这一点上，很明显你实际上正在使用一堆迭代器：一个指向节点的指针和反映搜索该节点子节点的当前进度的索引。使用像Java这样的语言，我们可以明确这一点。（不利的一面是，我们在处理子级时无法访问父项，这在某些情况下可能是一个问题。
在这里，我将使用一个单独的集合来保留访问的节点。这是更可取的，因为它使多个搜索和部分搜索变得更加简单。
void search(Node p) {
Set<Node> visited = new HashSet<>();
Deque<Iterator<Node>> stack = new ArrayDeque<>();
visited.add(p); // Visit the root.
stack.push(p.children.iterator());
while (!stack.isEmpty()) {
Iterator<Node> i = stack.pop(); // Backtrack to a child list with work to do.
while (i.hasNext()) {
Node child = i.next();
if (!visited.contains(child)) {
stack.push(i); // Save progress on this child list.
visited.add(child); // Descend to visit the child.
i = child.children.iterator(); // Process its children next.
}
}
}
}
作为最后的微优化，您可以跳过在堆栈上推送耗尽的迭代器（在 C 中，i child数组末尾的值），因为它们在弹出后被忽略。
void search(Node p) {
Set<Node> visited = new HashSet<>();
Deque<Iterator<Node>> stack = new ArrayDeque<>();
visited.add(p); // Visit the root.
if (!p.children.isEmpty()) stack.push(p.children.iterator());
while (!stack.isEmpty()) {
Iterator<Node> i = stack.pop(); // Backtrack to a child list with work to do.
while (i.hasNext()) {
Node child = i.next();
if (!visited.contains(child)) {
if (i.hasNext()) stack.push(i); // Save progress on this child list.
visited.add(child); // Descend to visit the child.
i = child.children.iterator(); // Process its children next.
}
}
}
}
这是一个java程序的链接，显示DFS遵循递归和非递归方法，并计算发现和完成时间，但没有边缘拉勒。
public void DFSIterative() {
Reset();
Stack<Vertex> s = new Stack<>();
for (Vertex v : vertices.values()) {
if (!v.visited) {
v.d = ++time;
v.visited = true;
s.push(v);
while (!s.isEmpty()) {
Vertex u = s.peek();
s.pop();
boolean bFinished = true;
for (Vertex w : u.adj) {
if (!w.visited) {
w.visited = true;
w.d = ++time;
w.p = u;
s.push(w);
bFinished = false;
break;
}
}
if (bFinished) {
u.f = ++time;
if (u.p != null)
s.push(u.p);
}
}
}
}
}
完整的来源在这里。这也是一个很好的视频，解释了DFS。
为了使用堆栈进行DFS遍历，请从堆栈中弹出一个节点（记住在堆栈中推送初始节点）并检查它是否已被访问。如果已经访问过，则忽略并弹出下一个，否则输出弹出的节点，标记它已访问并将其所有邻居推送到堆栈上。继续这样做，直到堆栈为空。