テクノロジ系 / アルゴリズムとプログラミング
深さ優先探索
深さ優先探索は、グラフや木で1つの枝を行けるところまで深く進み、戻りながら別の枝を調べる探索方法です。
別名・関連表記：DFS
もう少し詳しく
再帰やスタックを使って実装できます。幅優先探索が近い頂点から広く調べるのに対し、深さ優先探索は先に深い経路をたどります。行き止まりに到達したら直前の分岐まで戻り、未探索の枝を調べます。
試験での見方
例：迷路で右手法のように一方向へ進み、行き止まりなら戻って別の道を試します。
テクノロジ系 / アルゴリズムとプログラミング
深さ優先探索は、グラフや木で1つの枝を行けるところまで深く進み、戻りながら別の枝を調べる探索方法です。
別名・関連表記：DFS
再帰やスタックを使って実装できます。幅優先探索が近い頂点から広く調べるのに対し、深さ優先探索は先に深い経路をたどります。行き止まりに到達したら直前の分岐まで戻り、未探索の枝を調べます。
例：迷路で右手法のように一方向へ進み、行き止まりなら戻って別の道を試します。
深さ優先探索ではスタックまたは再帰を使う点を押さえます。探索順を問う問題では、隣接頂点をどの順で選ぶかも確認しましょう。