キューをBFS実装のスタックに変更した場合、DFSを取得しますか？

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 $

問題は、訪問時ではなく、プッシュ時に見られるようにマークするために発生します。コメントで指摘されているように、訪問時にマークを付けた場合、スペース要件は$ mathcal {o}（v）$ではなく、$ theta（v+e）$まで上昇する可能性があります。

私は同意します、問題は些細なことではありません。