Получаете ли вы DFS, если вы меняете очередь на стек в реализации BFS?

Вот стандартный псевдокод для поиска в ширину:

{ 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предполагаются операции очереди. Но что, если они являются стековыми операциями? Полученный алгоритм посещает вершины в порядке первой глубины?

Если бы вы проголосовали за комментарий «это тривиально», я бы попросил вас объяснить, почему он тривиален. Я нахожу проблему довольно сложной.

Нет, это не то же самое, что DFS.

Рассмотрим график

Если вы перемещаете узлы в порядке справа налево, алгоритм дает вам обход:

$A, B , E, C , D$

в то время как DFS будет ожидать, что это будет

$A,B,E,D,C$

$\Theta(V+E)$$\mathcal{O}(V)$

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