Tl; dr 是您不需要多个标志。
实际上，您可以通过显式执行编译器对运行时堆栈所做的操作，将递归 DFS 转换为迭代。该技术使用gotos 来模拟调用和返回，但这些可以转换为更具可读性的循环。我将在 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.
}
}
现在对代码做一些“代数”以开始摆脱gotos。
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.
}
}
}
}