У вас есть 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 $

Проблема возникает из -за того, что вы отмечаете это, как видно во время толкания, а не во время посещения. Как указывалось в комментариях, если вы отмечаете во время посещения, ваши пространственные требования могут подняться до $ theta (v+e) $, а не $ mathcal {o} (v) $.

Я согласен, проблема не тривиальна.