お疲れ様です！
前回は計算量（Big-O）の話を書きましたが、今回はその流れで、探索アルゴリズムの基本 DFS（深さ優先探索） と BFS（幅優先探索） をまとめてみました 
名前は難しそうですが、中身は 「スタックを使うか、キューを使うか」だけの違い です。
興味ある方は読んでいただけると嬉しいです 
前提：スタックとキューとは？
DFS / BFS の主役は、スタックとキューという2つのデータ構造です。
違いは 「取り出す順番」 だけです。
スタック（Stack）= 後入れ先出し（LIFO）
最後に入れたものから取り出す。積み上げた本のイメージです 
↓入れる ↑取り出す（最後に入れた[3]が先に出る）
┌─────┐
│ [3] │ ← 最後に入れた
│ [2] │
│ [1] │ ← 最初に入れた
└─────┘
身近な例：重ねたお皿、ブラウザの「戻る」ボタン
キュー（Queue）= 先入れ先出し（FIFO）
最初に入れたものから取り出す。レジの行列のイメージです。
入れる→ [1][2][3] →取り出す（最初に入れた[1]が先に出る）
身近な例：レジ待ち、順番待ちの行列
Rubyだと
Array でどちらも表現でき、違いは 「取り出す側」だけです。
# スタック（LIFO）… 末尾から取り出す
stack = []
stack.push(1); stack.push(2)
stack.pop # => 2（最後に入れたものが先）
# キュー（FIFO）… 先頭から取り出す
queue = []
queue.push(1); queue.push(2)
queue.shift # => 1（最初に入れたものが先）
入れるのはどちらも末尾（push）。違いは取り出しが pop（末尾）か shift（先頭）か だけ。
この小さな差が、このあと DFS / BFS の違いにそのまま効いてきます。
どんなときに使う？
R「親子・階層構造をたどる」場面です。
- カテゴリ（大カテゴリ → 中カテゴリ → 小カテゴリ）
- 組織図（部長 → 課長 → メンバー）
- コメントの返信ツリー（ネストする返信）
- 何かの依存関係をたどる
こういう 木（ツリー）やグラフ を「全部たどる」「最短で目的地を探す」ときに使うのが DFS / BFS です。
まず木（ツリー）をイメージする
こんなカテゴリツリーを例にします。
A
/ | \
B C D
/ \ \
E F G
このツリーを「上から全部たどる」とき、たどる順番が2種類あります。それが DFS と BFS です。
-
DFS（深さ優先） … 行けるところまで深く潜ってから戻る →
A → B → E → F → C → D → G -
BFS（幅優先） … 同じ階層を全部見てから次の階層へ →
A → B → C → D → E → F → G
DFSは「とりあえず一番奥まで行ってみる人」、BFSは「同じ階を全部見てから次の階に行く人」、というイメージです。
DFS（深さ優先）= スタック / 再帰
DFSは 「行けるところまで潜る」 ので、一番手軽なのは再帰です。
def dfs(category)
puts category.name
category.children.each { |child| dfs(child) } # 子に潜っていく
end
dfs(root) # => A, B, E, F, C, D, G
再帰は、実は裏で コールスタック（メソッド呼び出しを積むスタック）を使っています。
つまり DFS の正体は「スタック」 です。自前のスタックでも書けます👇
def dfs(root)
stack = [root]
until stack.empty?
node = stack.pop # ★末尾から取り出す（あとに入れたものが先）
puts node.name
stack.concat(node.children)
end
end
BFS（幅優先）= キュー
BFSは 「同じ階層から順に」 見ていくので、キューを使います。
def bfs(root)
queue = [root]
until queue.empty?
node = queue.shift # ★先頭から取り出す（先に入れたものが先）
puts node.name
queue.concat(node.children)
end
end
bfs(root) # => A, B, C, D, E, F, G
実は違いは「1行」だけ
さっきの2つのコードを並べると、違いはここだけです。
node = stack.pop # DFS … 末尾から取り出す＝スタック（LIFO）
node = queue.shift # BFS … 先頭から取り出す＝キュー（FIFO）
DFS と BFS の差は「スタックか、キューか」だけ。
pop（末尾）かshift（先頭）か、ただそれだけで、たどる順番がガラッと変わります。
（前回ふれた「スタックとキュー」がそのまま効いてくる話ですね）
どっちを使う？
| DFS（深さ優先） | BFS（幅優先） | |
|---|---|---|
| データ構造 | スタック（再帰） | キュー |
| 得意なこと | 全部たどる／深い構造をたどる | 最短経路を求める／浅いところを優先 |
| 例 | 「全カテゴリを列挙」「依存を全部たどる」 | 「最短で何ステップか」「一番近い該当を探す」 |
「最短距離・最小ステップ数」を知りたいなら BFS が定番です。
BFSは近い順に探すので、最初に見つかった経路が必ず最短になります。
計算量（Big-O）
どちらも、全ノード（頂点 V）と全つながり（辺 E）を1回ずつ見るので、計算量は O(V + E) です（木なら O(n)）。
DFSもBFSも、たどる順番が違うだけで計算量は同じです。
注意点：Railsでやりがちな罠
① children のたびにSQL → N+1
category.children.each { |child| dfs(child) } # 階層をたどるたびにクエリが飛ぶ💥
ツリーをたどるコードは、ノードごとに children を引いてN+1になりがちです。
件数が増えると、まさに前回のBig-Oの世界（クエリが O(n) 回）。全件を1クエリで取ってからメモリ上でツリーを組む、もしくは ancestry などの階層管理gemを使うのが定番です。
② DFS（再帰）は深すぎると SystemStackError
再帰DFSはコールスタックを積むので、階層が極端に深いとスタックオーバーフローします。深さが読めないデータでは、自前スタックのループ版にすると安全です。
③ BFS は横に広いとキューが膨らむ
BFSは「次の階層のノード」をキューに溜めるので、横に広いツリーだとキューが大きくなり、メモリを食います。
（このあたりはメモリの記事とも繋がります）
最後に
DFSとBFSは、名前こそ難しそうですが、「スタックで深く潜るか、キューで横に広げるか」だけの違いです。
- DFS = スタック（再帰）。全部たどる・深い構造向き
- BFS = キュー。最短経路・近い順に探すのが得意
そして実務で効いてくるのは、アルゴリズムそのものより 「ツリーをたどる＝N+1になりやすい」「深い再帰＝スタックオーバーフロー」「広いBFS＝メモリ増」 といった周辺の罠だったりします。
N+1や深い再帰の地雷を踏んでいないかぜひ意識してみてください！