做你得到DFS如果你改变的队列中的一个堆叠在一BFS的执行？

Question

这里是标准代码对广度第一搜索：

{ seen(x) is false for all x at this point }
push(q, x0)
seen(x0) := true
while (!empty(q))
  x := pop(q)
  visit(x)
  for each y reachable from x by one edge
    if not seen(y)
      push(q, y)
      seen(y) := true

在这里， push 和 pop 是假定为被排队操作。但是，如果他们是堆操作的?不得算法访问的顶点在深度优先秩序？

---

如果你投票赞成的评论，"这是微不足道"，我要求你解释为什么它是微不足道的。我找到问题的相当棘手。

Answer 1

不，这不是同一个DFS。

考虑图

如果你按节点在右到左的顺序，算法给你一遍历：

$A、B、E,C,D$

同时DFS会希望它是

$A、B、E,D,C$

问题的发生是因为你标记为看到当时的推动，而不是在时间的访问。如指出的评论，如果你标记的时间访问，你的空间需求可能会去$ heta(V+E)$而不是$\mathcal{O}(V)$.

我同意,问题不是微不足道的。