テクノロジ
深さ優先探索とは
読み方：ふかさゆうせんたんさく
ひとことで言うと：一つの経路をできるだけ深く進み、行き止まりで戻るグラフ探索法。
意味をわかりやすく解説
深さ優先探索（DFS）は、ある頂点から一つの経路を行けるところまで進み、進めなくなったら直前の分岐点へ戻って別の経路を調べる探索方法です。
再帰呼出しまたはスタックで実装できます。グラフに閉路がある場合は訪問済み頂点を記録しないと同じ場所を繰り返す可能性があります。
具体例
迷路で右の道を選んだら行き止まりまで進み、戻って次の未探索の道を試す動きがDFSです。
似た用語との違い
幅優先探索
DFSは深く進み、スタックまたは再帰を使います。BFSは近い頂点から調べ、キューを使います。
バックトラッキング
バックトラッキングはDFS的に候補を進み、条件に合わなければ戻って別候補を試す探索設計です。
覚え方
DFS＝Deep＝深く。スタックで戻り道を覚えます。
基本情報技術者試験の試験ポイント
スタック/再帰との対応、訪問順序、閉路を持つグラフでのvisited管理を押さえます。
CHECK QUESTION
DFSを反復処理で実装するとき、未探索頂点の管理に使う代表的なデータ構造は何ですか。
答えを見る
スタックです。LIFOにより最後に見つけた頂点から深く探索します。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。