depth first search

depth first search（深さ優先探索）は、グラフや木構造の探索において、ある方向へ行けるところまで突き進み、行き止まりに達した時点で一つ前の分岐点まで戻って別の道を試すという戦略的なアプローチです。この手法は、特に解が深い階層にあることが予想される場合や、迷路の脱出経路を探索する場合に非常に有効です。

幅優先探索との対比

breadth first search（幅優先探索）が現在の階層にあるすべての隣接ノードを均等に確認してから次の階層へ進むのに対し、depth first searchは一つの道を最深部まで優先的に掘り下げます。そのため、メモリ消費量において、探索木の幅が非常に広い場合にはdepth first searchの方が効率的である傾向があります。一方で、最短経路を確実に最初に見つけたい場合は、breadth first searchの方が適しています。

実装上の特徴と注意点

実装においては、再帰関数を利用するか、スタック（後入れ先出し）構造を用いるのが一般的です。再帰的に実装する場合、探索する深さが極端に深いとスタックオーバーフローが発生する可能性があるため、データ構造の規模に応じた適切な実装方法を選択する必要があります。また、グラフにサイクル（循環）が含まれている場合、一度訪れたノードを記録しておかないと無限ループに陥るため、訪問済みフラグの管理が不可欠です。