DFS（深度优先搜索）与 BFS（广度优先搜索）空间优化

Question

问题

我目前正在深入研究 DFS 和 BFS 算法的经典迭代方法的一些优化。我目前在大学使用的材料介绍了两种迭代方法，如下所示。

定义：

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

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

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

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

提出迭代方法：

这些是我大学课程材料中提出的算法：

BFS

BFS-Iterative(A,v,u,i): // on vertex i
queue <- new Queue()
markInUse(u,i) // sets u[k] = 1
queue.enqueue(i)
while not queue.empty():
    k <- queue.dequeue()
    markAsVisited(v,i)
    for j in A[k]:
        if isNotInUse(u,j) and isNotVisited(v,j): // checks if u[k] = 1
            markInUse(u,j)
            queue.enqueue(j)

这里的空间复杂度是 O(|V|)，这要归功于“使用中”数组 u 的使用，这确保了没有顶点（索引）被多次推入队列中。

DFS

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)

根据材料，这里的空间复杂度是 O(|E|)，并且可以通过将迭代器推入堆栈（或指向列表的指针）而不是所有邻居来模拟与递归算法相同的行为来改进它。一个特定的顶点，我也成功实现了（此处未显示）。

问题

材料指出，使用数组来跟踪向量 u 中“使用中”的顶点的“技巧”对于 DFS 不起作用，留给读者去发现为什么。

为什么以下使用“使用中”数组方法的修改算法不起作用？这是my的实现，因为材料没有显示这个算法，所以只提到了它。我在几个简单的例子上运行了它，效果很好。我在这里缺少什么？

DFS-Iterative-Modified(A,v,u,i): // same structure as BFS-Iterative-Modified
stack <- new Stack() // same as above, using now stack instead of queue
markInUse(u,i)
stack.push(i)
while not stack.empty():
    k <- stack.pop()
    if isNotVisited(v,i):
        markAsVisited(v,i)
        for j in A[k]:
            if isNotInUse(u,j):
                markInUse(u,j)
                stack.push(j)

这似乎也可以将 DFS 算法从 O(|E|) 改进到 O(|V|)，但也许我只需要一个反例来理解为什么它是错误的。

Answer 1

您的实现中存在一些错误，但我会假装它们不存在来回答您的问题...

当您访问父级时，通过推送子级并将它们标记为“正在使用”，如果这些子级会更早出现，您可能会弄乱 DFS 顺序。

例如，给定此图：

  B--C
 /
A-D
 \
  C

您的算法可以按 A、B、D、C 的顺序访问节点，但这不是 DFS 顺序。发生这种情况是因为，当您访问 A 时，它的所有子项都会被推送并标记为正在使用。当 B 被访问时，C 无法被推送，因为它被标记为正在使用，因此它可能不会在 D 之前被访问。