迭代深度优先搜索 (DFS) 的空间优化

Question

问题

在大多数学术文献中，首选的 DFS 算法始终是递归的，但是，对于大型图，使用堆栈的迭代变体对我来说似乎更实用，而且不会产生任何堆栈溢出危险。

然而，找到一种能够正确模仿递归行为并保证顶点数量的 O(|V|) 的迭代实现似乎令人畏惧。

因此，我提出了自己的实现，想知道它是否正确，以及您是否会使用这个实现，不仅在实际应用中，而且在技术面试中，当被要求使用非递归版本的 DFS 时。

定义：

G(V,E)：将在其上运行算法的连通图，具有一组 V 的顶点和一组 E 的边。

A[1...n]：图中每个顶点的邻接列表数组（A[k]是包含顶点k的相邻顶点的链表）

v[1...n]：跟踪访问过的顶点的数组

u[1...n]：跟踪活动顶点的数组（已进入正在使用的数据结构的顶点）

没有优化空间的 DFS 迭代，时间复杂度为 O(|E|)：

DFS-Iterative(A,v,i): // on vertex i
stack <- new Stack()
stack.push(i)
while not stack.empty():
    k <- stack.pop()
    if isNotVisited(v,k): // checks if v[k] = 1
        markVisited(v,k) // sets v[k] = 1
        for j in A[k]:
            if isNotVisited(v,j):
                stack.push(j)

优化空间的 DFS 迭代，时间复杂度为 O(|V|)：

这里的邻接列表是指向列表第一个元素的指针。列表的每个节点都有两个成员变量“next”和“value”。

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 的标准迭代实现吗？

Answer 1

是的，您的实施是正确的。我只想更改参数列表。

V

只需要在函数本身执行期间存在；调用者不需要提供它：这与堆栈的情况非常相似。

所以：

DFS-Iterative-Optimized(A, i):
    V <- new Set()  // or Array<bool>
    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])