歡迎來到圖遍歷（Graph Traversal）的世界！

在本章中，我們將學習電腦如何「走遍」一個圖（graph）來尋找資訊。無論是 Google 地圖幫你找出前往最愛披薩店的最快路線，還是 Facebook 向你推薦新朋友，圖遍歷演算法都是實現這些功能的幕後功臣。

如果一開始覺得圖看起來有點雜亂，別擔心——看完這些筆記後，你就會發現它們其實就是等待被破解的邏輯謎題！

先修知識：什麼是圖（Graph）？

在我們進行「遍歷」（Traverse，其實就是「訪問」的高級說法）之前，先來複習一下圖的組成：

  • 頂點（Vertices 或 Nodes）： 圖中的點或「圓圈」（就像地圖上的城市）。
  • 邊（Edges 或 Arcs）： 連接節點的線（就像城市之間的道路）。

1. 廣度優先搜尋（Breadth-First Search，簡稱 BFS）

你可以把 廣度優先搜尋 想像成「池塘裡的漣漪」。你從一個點出發，先探索所有最近的鄰居，然後再擴散到下一層，以此類推。

「逐層推進」策略

BFS 採用 逐層（layer by layer） 方式探索圖。你會先訪問距離為 1 的所有節點，接著是距離為 2 的所有節點，等等。為了記錄接下來要訪問哪些節點，BFS 會使用 佇列（Queue） 資料結構（先進先出，First-In, First-Out）。

步驟詳解：

1. 選擇一個起始節點，並將其標記為 已訪問（visited）。
2. 將所有 直接相鄰的鄰居 加入 佇列（Queue）。
3. 從佇列中取出第一個節點。
4. 如果該節點尚未被訪問，則將其標記為已訪問，並將 該節點的所有鄰居 加入佇列的末端。
5. 重複以上步驟，直到佇列為空。

現實生活中的比喻：社交媒體搜尋

想像你在 LinkedIn 上搜尋某人。首先，你會查看你的 直接聯繫人（距離為 1）。如果找不到，你再查看 聯繫人的聯繫人（距離為 2）。這就是先「廣泛」地搜尋，再深入探索。

典型應用：最短路徑

由於 BFS 會優先探索鄰近的節點，它是尋找 無權圖（unweighted graph）（即每條路長度都一樣的圖）中 最短路徑 的絕佳工具。它能保證當你找到目標時，所經過的邊數是最少的。

重點速記：BFS
  • 資料結構： 使用 佇列（Queue）。
  • 搜尋風格： 廣闊/寬度。
  • 最佳用途： 尋找 最短路徑。

2. 深度優先搜尋（Depth-First Search，簡稱 DFS）

如果說 BFS 像漣漪，那麼 深度優先搜尋 就好比一個在黑暗洞穴中探險的探險家。你會選擇一條路一直走到底，直到遇到死胡同，然後 回溯（backtrack） 到上一個分岔路口，再嘗試另一條路。

「深入探索」策略

DFS 會在移動到下一條分支前，徹底探索當前的一條分支。為了管理此過程，DFS 使用 堆疊（Stack） 資料結構（後進先出，Last-In, First-Out）或 遞迴（Recursion）。

步驟詳解：

1. 選擇一個起始節點，並將其標記為 已訪問（visited）。
2. 移動到一個 尚未訪問的相鄰鄰居。
3. 重複步驟 2，直到到達一個沒有未訪問鄰居的節點（死胡同）。
4. 回溯（Backtrack） 到前一個節點，並檢查是否有其他未訪問的鄰居。
5. 當你回溯到起點且所有節點都已訪問完畢時，過程結束。

現實生活中的比喻：走出迷宮

AQA 課程大綱中提到的 走迷宮 是 DFS 最經典的應用。你在走廊裡一直往前走直到撞牆，然後回頭嘗試剛才經過的分岔路口。你不會同時嘗試所有的走廊，而是先走完一條路。

典型應用：迷宮求解與遊戲邏輯

DFS 非常適合用於 迷宮導航 或那些需要判斷長路徑盡頭是否有解的謎題。它比 BFS 使用更少的記憶體，因為它只需要記錄當前路徑上的節點。

重點速記：DFS
  • 資料結構： 使用 堆疊（Stack）（或遞迴）。
  • 搜尋風格： 深度。
  • 最佳用途： 走迷宮。

比較 BFS 與 DFS

考試中很常要求你在兩者之間做出選擇。以下是一個記住兩者區別的簡單方法：

記憶小技巧：字母法
- BFS = Breadth（廣度，向「寬」處搜尋）
- DFS = Depth（深度，向「深」處搜尋）

常見陷阱：

  • 忘了標記節點： 如果你不將節點標記為「已訪問」，電腦可能會繞圈圈陷入死循環（無限迴圈）！
  • 佇列 vs. 堆疊： 學生常會搞混這兩個。記住：BFS 用 Queue（排隊等候以便進行廣度擴張），DFS 用 Stack（把路徑堆疊起來以便深入探索）。

總結

圖遍歷 是許多複雜演算法的基礎。請為你的 AQA 考試記住這兩大重點：

1. 廣度優先搜尋 (BFS) 使用 佇列 (Queue)，透過優先檢查所有鄰居來尋找 無權圖中的最短路徑。

2. 深度優先搜尋 (DFS) 使用 堆疊 (Stack)，將路徑探索到底，是 迷宮導航 的經典方法。

如果剛開始追蹤這些步驟覺得很慢，別擔心。拿張紙和筆，畫幾個節點，試著用佇列或堆疊實際「走」一遍。你很快就會領悟其中的竅門！