幅優先探索と深さ優先探索ってなぁに

28 Sep, 2025

(GPTコピペ)

🌳 幅優先探索 (BFS: Breadth-First Search)

• 横に広がっていく探索。
• ルート（スタート）から近いノードを順番に全部見て、その次に1段下のノードへ進む。
• 探索イメージ 👉 「波が広がる」感じ 🌊
• キュー（FIFO）を使うのが定番。

💡 特徴：

• 最短経路を見つけるのに強い。
• でも、探索範囲が広がるからメモリ消費が大きくなる。

🌌 深さ優先探索 (DFS: Depth-First Search)

• 奥へ奥へと潜っていく探索。
• 一つの道をとことん行けるところまで進んで、行き止まりになったら戻って別の道を試す。
• 探索イメージ 👉 「迷路で突き進む」感じ 🌀
• スタック（LIFO）や再帰を使う。

💡 特徴：

• メモリ効率がいい。
• でも、遠回りしてゴールにたどり着くこともある（最短ルートを保証しない）。

🏃‍♀️ 例：迷路で考えると…

• BFS → 入口から1歩先のマス全部 → 2歩先全部…って調べる。必ず最短ルートを見つける。
• DFS → ひたすら右に進んで、行き止まりなら戻ってやり直す。早く見つかることもあれば、めっちゃ遠回りになることも。

✨まとめると：

• BFS = 広く浅く → 最短距離探すのに便利
• DFS = 狭く深く → メモリ節約・すぐ終わることも

#tech