辛苦了！
前回我寫了計算量（Big-O）的話，這次延續那個主題，整理一下探索演算法的基本 DFS（深度優先搜尋） 和 BFS（廣度優先搜尋） 
名字看起來很難，但內容其實只是 「用堆疊還是用佇列」的差別。
如果有興趣的話，歡迎讀讀看 
前提：堆疊與佇列是什麼？
DFS / BFS 的主角，是 堆疊 和 佇列 這兩種資料結構。
差別只有 「取出的順序」 而已。
堆疊（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 的差別。
什麼時候會用到？
在「沿著父子、階層結構往下追」的場景中會用到。
- 分類（大分類 → 中分類 → 小分類）
- 組織圖（部長 → 課長 → 成員）
- 留言回覆樹（巢狀回覆）
- 追蹤某些依賴關係
像這樣的 樹（tree）或圖（graph），要做「全部走訪」或「找出最短路徑」時，就會用到 DFS / BFS。
先看樹（Tree）的概念
以這樣的分類樹為例。
A
/ | \
B C D
/ \ \
E F G當你要「從上往下全部走訪」時，會有 兩種走訪順序。這就是 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
endBFS（廣度優先）= 佇列
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 行」
把剛剛兩段程式並排看，差別就只有這裡。
node = stack.pop # DFS … 從尾端取出＝堆疊（LIFO）
node = queue.shift # BFS … 從前端取出＝佇列（FIFO）DFS 和 BFS 的差別，就只是「堆疊還是佇列」。
pop（尾端）還是shift（前端），只差這一點，走訪順序就會完全不同。
（也就是前面提到的「堆疊與佇列」在這裡直接派上用場）
該用哪一個？
| DFS（深度優先） | BFS（廣度優先） | |
|---|---|---|
| 資料結構 | 堆疊（遞迴） | 佇列 |
| 擅長的事 | 全部走訪／追蹤深層結構 | 求最短路徑／優先找淺層 |
| 例子 | 「列出所有分類」「把依賴全部追完」 | 「幾步內能到」「找最近的符合項目」 |
如果你想知道 「最短距離、最少步數」，那通常會選 BFS。
BFS 會按照距離由近到遠搜尋，所以第一次找到的路徑一定是最短的。
計算量（Big-O）
兩者都會把 所有節點（頂點 V）與所有連結（邊 E） 各看一次，所以計算量是 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)）。比較常見的做法是先用一個查詢把全部資料抓出來，再在記憶體中組成樹狀結構，或是使用像 ancestry 這類階層管理的 gem。
② DFS（遞迴）太深時會發生 SystemStackError
遞迴 DFS 會把 呼叫堆疊 一層層堆上去，所以如果階層非常深，就可能發生 堆疊溢位。
對於深度無法預先知道的資料，建議改成自己手寫堆疊的迴圈版本，比較安全。
③ BFS 在橫向很寬時佇列會膨脹
BFS 會把「下一層的節點」先存進佇列，所以如果樹在橫向非常寬，佇列會變得很大，吃掉很多記憶體。
（這部分也和記憶體的文章有關）
最後
DFS 和 BFS 的名字雖然看起來很難，但其實只是 「用堆疊往深處走，還是用佇列往橫向展開」 的差別而已。
- DFS = 堆疊（遞迴）。適合全部走訪、深層結構
- BFS = 佇列。適合找最短路徑、按距離由近到遠搜尋
而在實務上真正容易踩雷的，往往不是演算法本身，而是像 「走樹狀結構很容易變成 N+1」「遞迴太深會堆疊溢位」「BFS 太寬會增加記憶體」 這些周邊問題。
請務必留意自己是否踩到 N+1 或深層遞迴的地雷！
1) --- 會變成分隔線（上一行必須是空白）
2) # 會變成一級標題
3) ## 會變成二級標題
4) ### 會變成三級標題
5) **粗體文字**會顯示粗體文字
6) ```當第一行與最後一行會顯示程式碼
7) 請搜尋 Markdown 語法，了解各種格式
