算法伪代码 #

Traverse(G, v):
    S is stack
    stack.push(v)
    label v as visited
    while S is not empty:
        v = S.pop()
        for all w in G.adjacentNodes(v) do:
            if w is not labeled:
                label w
                S.push(w)

算法特性简述 #

该遍历算法与BFS的核心区别是用栈替代队列，与标准迭代式DFS的区别则是标记已访问顶点的时机：标准DFS通常在弹出栈时标记顶点，而此算法在压栈前就完成标记，最终遍历顺序也和二者均不相同。

技术问题解答 #

1. 该遍历算法是否适用于任意复杂度的图？即能否访问初始顶点v所在连通分量中的全部顶点？ #

可以遍历初始顶点v所在连通分量的所有顶点，不受图的复杂度（有向/无向、带环/无环、简单/复杂）影响。

关键逻辑：

• 所有顶点在压入栈前就被标记为已访问，既避免了重复压栈导致的死循环，也保证每个可达顶点仅被处理一次。
• 栈的LIFO特性确保，只要顶点与v连通，必然会通过某个邻接节点被发现并压入栈，最终被弹出处理。即便是带环的图，由于标记时机提前，不会重复处理环上节点，也不会遗漏任何连通顶点。

2. 何时应优先选用DFS而非该遍历算法？原始DFS会在栈中产生重复元素，这是否具备优势？ #

优先选择标准DFS的场景集中在依赖回溯操作或特定遍历顺序的需求：

• 回溯类任务：比如寻找两点间的所有路径、迷宫求解、枚举子图等。标准迭代式DFS在弹出栈时标记顶点，栈中会保留未完全探索的节点——处理完一个节点的某条邻接分支后，还能回到该节点探索其他分支，这是回溯的核心能力。而此算法压栈时就标记，一旦离开节点就无法回溯，无法完成这类任务。
• 特定遍历顺序需求：比如后序遍历、拓扑排序（递归DFS天然适配）、计算顶点后置时间戳等。此算法的遍历顺序是“压栈即标记，弹出即处理”，更接近反向前序遍历，很难直接实现后序这类需要等待所有子节点处理完毕再处理父节点的逻辑，而标准DFS可以轻松做到。

关于标准DFS栈中重复元素的优势：
这种“重复”本质是路径探索的痕迹——栈内元素代表当前正在探索的路径分支。例如寻找路径时，栈内元素就是从起点到当前节点的完整路径；当某条分支走不通时，弹出节点即可回溯到上一节点切换分支。而此算法的栈中仅包含未处理的新节点，没有路径信息，完全无法支持回溯类操作。此外，在检测环路时，这种重复压入（弹出时才标记）的特性还能帮助记录环的具体走向，便于定位环路路径。

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