【要約】Railsで学ぶ DFS / BFS 入門 〜「深さ優先」と「幅優先」で木構造をたどる〜 [Qiita_Trend] | Summary by TechDistill
> Source: Qiita_Trend
Execute Primary Source
// Problem
開発者が階層構造（カテゴリ、組織図、コメントツリー等）を走査する際、適切なアルゴリズムや実装手法を選択できず、システムパフォーマンスを低下させる問題がある。具体的には以下のリスクが挙げられる。
- ・階層をたどるたびにSQLを発行し、N+1問題を引き起こす。
- ・再帰的なDFSの実装により、深い階層でSystemStackErrorが発生する。
- ・幅の広いツリーに対してBFSを用いると、キューが肥大化しメモリを圧迫する。
// Approach
スタックとキューというデータ構造の特性を利用し、探索目的に応じたアルゴリズムの使い分けを提示している。具体的な手法は以下の通りである。
- ・DFS（深さ優先探索）: スタック（LIFO）または再帰を用い、行けるところまで深く探索する。
- ・BFS（幅優先探索）: キュー（FIFO）を用い、同じ階層を順に探索して最短経路を特定する。
- ・Railsでの対策: ancestry等のgem利用や、メモリ上でのツリー構築によるN+1の回避を推奨する。
// Result
開発者が探索アルゴリズムの特性と、それに関連する実行時リスクを理解できる。これにより、以下の改善が期待できる。
- ・最短距離・最小ステップ数を知りたい場面でのBFSの適切な選択。
- ・再帰によるスタックオーバーフローを避けるための、自前スタックを用いたループ実装への切り替え。
- ・N+1問題の回避による、データベース負荷の軽減。
Senior Engineer Insight
> アルゴリズムの計算量 O(V + E) は理論上重要だが、実務ではI/Oとメモリが支配的だ。Railsでのツリー走査は、アルゴリズムの選択以上に、N+1の回避とメモリ消費の制御が成否を分ける。特に大規模な階層データでは、再帰を避け自前スタックでループを回す、あるいは階層管理専用のライブラリを採用する判断が、システムの安定稼働には不可欠である。