
幅優先探索で訪問済みにするタイミング
解き方
幅優先探索は、開始点から近い頂点を順に調べる方法です。キューは先に入れたものを先に取り出す入れ物で、訪問済み配列は「この頂点をすでに発見したか」を記録します。辺の重みがすべて同じ場合、最初に発見した経路の辺の本数が最小になります。
手順を追う例
無向グラフで、辺をA―B、A―C、B―D、C―Dとします。隣接頂点はアルファベット順に調べます。最初にAを訪問済みにしてキューへ入れます。
Aを取り出す:B、Cをそれぞれ訪問済みにして追加。キューは[B,C]。
Bを取り出す:Dを訪問済みにして追加。キューは[C,D]。
Cを取り出す:Dは訪問済みなので追加しない。キューは[D]。
Dを取り出す:新しい頂点はなく終了します。
取り出す順番はA、B、C、Dです。Dまでの距離は2本ですが、A→B→DとA→C→Dのどちらも同じ長さです。
確認問題【オリジナル】
上のグラフで、訪問済みの印を「キューから取り出した瞬間」だけ付けることにし、追加時には未訪問なら何度でも追加するとします。Bを取り出した後、次にCを取り出したとき、Dはどう扱われますか。追加時に印を付ける方式との違いを答えてください。
答えと解説
Cを処理する時点ではDはまだ取り出されておらず、未訪問のままです。そのためDがもう一度追加され、キューは[D,D]になります。取り出したときに重複を捨てる実装も可能ですが、余分な追加が発生します。発見した時点、つまりキューへ入れるときに印を付ける方式なら、各頂点を原則1回だけ追加できます。
問題では「訪問」の意味を、発見なのか処理完了なのか先に確認します。また、隣接頂点を調べる順番が変わると同じ距離の頂点の処理順や親は変わり得ます。幅優先だから頂点名の順になるわけではありません。
本記事の例と確認問題は独自に作成しています。