迭代深度优先搜索（DFS）空间优化实现的正确性与标准性问询

一、两种迭代DFS实现的正确性验证 #

1. 非空间优化版本（空间复杂度O(|E|)） #

这个实现是正确的，能够完成连通图的深度优先遍历：

• 核心逻辑：借助栈存储待访问节点，弹出节点时若未被访问则标记为已访问，随后将该节点所有未访问的邻接节点压入栈中。
• 注意：它的遍历顺序与递归DFS可能存在差异——递归DFS会严格按照邻接表顺序优先处理第一个未访问邻接点，而此版本因栈的后进先出特性，会逆序处理邻接节点，但这属于DFS的合法变体，不影响遍历的完整性和正确性。
• 空间复杂度标注准确：最坏场景下（例如完全图），每个节点的所有邻接节点都会被压入栈，栈内元素总数可达O(|E|)级别。

对应的代码实现：

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]是否为1
        markVisited(v,k) // 将v[k]设为1
        for j in A[k]:
            if isNotVisited(v,j):
                stack.push(j)

2. 空间优化版本（空间复杂度O(|V|)） #

这个实现同样正确，且确实将空间复杂度控制在了O(|V|)：

• 核心思路：不再直接压入所有邻接节点，而是用栈保存邻接表的遍历指针（记录当前遍历到邻接表的哪个位置）。每次弹出指针时，先将下一个指针压回栈以保存遍历进度，再处理当前指向的节点；若节点未被访问，则标记并压入该节点的邻接表头指针，继续深度遍历。
• 空间复杂度的合理性：每个节点的邻接表只会被压入栈一次，栈中同时存在的指针数量最多等于当前遍历路径的长度（即DFS的深度，最坏为|V|），不会出现O(|E|)级别的空间膨胀。

对应的代码实现：

DFS-Iterative-Optimized(A,v,i):
stack <- new Stack()
markVisited(V,i)
stack.push(A[i])
while not stack.empty():
    curList <- stack.pop()
    if curList:
        stack.push(curList->next)
        k <- curList->value
        if isNotVisited(V,k):
            markVisited(V,k)
            stack.push(A[k])

二、空间优化版本是否为标准实现 #

这种通过保存邻接表遍历状态（指针/迭代器）的迭代DFS，是工业界和学术领域中常用的标准空间优化实现。它完美模拟了递归DFS的调用栈行为——递归时函数调用栈会自动保存当前邻接表的遍历位置，返回后继续处理剩余邻接点；而此版本用显式栈手动维护这一状态，既避免了递归带来的栈溢出风险，又严格控制了空间开销，是处理大型图DFS的首选方案之一。

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