为何迭代DFS无法复用BFS的in-use数组空间优化方案？

定义 #

• G(V,E)：待遍历的连通图，V为顶点集，E为边集
• A[1...n]：图的邻接表数组，A[k]为顶点k的邻接顶点链表
• v[1...n]：已访问顶点标记数组
• u[1...n]：活跃顶点标记数组（已进入数据结构的顶点）

课程给出的迭代实现 #

BFS #

BFS-Iterative(A,v,u,i): // 从顶点i开始遍历
queue <- new Queue()
markInUse(u,i) // 将u[i]设为1
queue.enqueue(i)
while not queue.empty():
    k <- queue.dequeue()
    markAsVisited(v,k)
    for j in A[k]:
        if isNotInUse(u,j) and isNotVisited(v,j): // 检查u[j]是否为0
            markInUse(u,j)
            queue.enqueue(j)

该实现通过u数组确保每个顶点仅入队一次，空间复杂度为O(|V|)。

DFS #

DFS-Iterative(A,v,i): // 从顶点i开始遍历
stack <- new Stack()
stack.push(i)
while not stack.empty():
    k <- stack.pop()
    if isNotVisited(v,k): // 检查v[k]是否为0
        markVisited(v,k) // 将v[k]设为1
        for j in A[k]:
            if isNotVisited(v,j):
                stack.push(j)

该实现空间复杂度为O(|E|)，可通过栈存储迭代器优化（已实现）。

问题与修改后的算法 #

课程指出，BFS所用的"in-use"数组跟踪活跃顶点的优化技巧不适用于DFS。我尝试实现了如下修改后的迭代DFS算法，在简单测试中运行正常，但不解为何该方案不可行：

DFS-Iterative-Modified(A,v,u,i): // 结构模仿BFS的优化版本
stack <- new Stack() // 替换队列为栈
markInUse(u,i)
stack.push(i)
while not stack.empty():
    k <- stack.pop()
    if isNotVisited(v,k):
        markAsVisited(v,k)
        for j in A[k]:
            if isNotInUse(u,j):
                markInUse(u,j)
                stack.push(j)

该修改版看似能将DFS空间复杂度从O(|E|)降至O(|V|)，但遗漏了什么？

反例与原因解释 #

反例1：后序遍历场景失效 #

考虑如下树形图：

1
├─ 2
│  └─ 4
│     └─ 5
└─ 3

邻接表：

• A[1] = [2, 3]

• A[2] = [1, 4]

• A[4] = [2, 5]

• A[5] = [4]

• A[3] = [1]

• 递归DFS的后序遍历结果：5 → 4 → 2 → 3 → 1（子节点处理完毕后才处理父节点，符合DFS回溯特性）

• 修改后的迭代DFS访问顺序：1 → 3 → 2 → 4 → 5（弹出顶点即标记为访问，无法等待子节点处理完成再处理父节点）

若基于该修改算法生成后序遍历，结果与递归DFS完全不符，无法满足拓扑排序、表达式树计算等依赖后序遍历的场景。

反例2：环检测逻辑失效 #

考虑环形图：1→2→3→1，邻接表：

• A[1] = [2]

• A[2] = [3]

• A[3] = [1]

• 递归DFS：访问3时，发现邻接的1已处于当前递归栈中（即遍历路径的父节点），可直接检测到环，路径为1→2→3→1。

• 修改后的迭代DFS：

  1. 标记u[1]=1，压入栈
  2. 弹出1，标记v[1]=1，将2标记为in-use并压栈
  3. 弹出2，标记v[2]=1，将3标记为in-use并压栈
  4. 弹出3，标记v[3]=1，遍历1时发现u[1]=1，直接跳过
  5. 栈空，遍历结束

该算法无法检测到环，因为u数组仅标记顶点是否入过栈，无法区分“已处理完毕的顶点”和“当前遍历路径中的顶点”，丢失了DFS跟踪递归栈的核心能力。

核心原因 #

BFS的u数组符合其层级遍历的特性：每个顶点仅需被处理一次，入队后不会再被其他路径重复入队。但DFS的核心是回溯遍历，需要允许顶点在未被处理时，通过不同路径多次入栈，以维持遍历的深度优先特性。u数组的存在直接阻止了这种行为，导致：

1. 遍历顺序完全偏离递归DFS，丢失了“深度优先、回溯”的核心特性；
2. 无法处理依赖递归栈状态的场景（如后序遍历、环检测、强连通分量计算等）；
3. 虽降低了空间复杂度，但算法已不再是标准DFS，而是一种栈实现的BFS变种，失去了DFS的适用场景价值。

内容的提问来源于stack exchange，提问作者Michel H