歡迎來到圖論（Graphs）的世界！
在本章中，我們將探討一種最強大且靈活的資料組織方式：圖（Graphs）。別擔心，這可不是你在數學課上看到的長條圖或折線圖！在電腦科學中，圖是用來表示不同事物之間如何相互連接的一種方式。
試想一下 Facebook 的好友關係、Google 地圖的導航，甚至是網際網路本身的連接方式——這些都是現實生活中圖的應用例子。讀完這些筆記後，你將了解電腦是如何「看待」這些連接，以及如何在其中進行搜尋和導航。
1. 什麼是圖（Graph）？
簡單來說，圖就是一組「點」和連接這些點的「線」。在電腦科學中，我們使用特定的術語來稱呼它們：
- 頂點（Vertices 或 Nodes）： 這些就是代表物件（如城市、人物或網頁）的「點」。單數形式稱為頂點（Vertex）。
- 邊（Edges 或 Arcs）： 這些就是連接頂點的「線」。它們代表了頂點之間的關係（例如城市之間的道路，或人與人之間的友誼）。
現實生活中的類比
想像一張地鐵系統地圖。每個車站就是一個頂點，連接它們的路軌就是邊。圖能幫助我們理解如何從車站 A 到達車站 B。
關鍵重點：
圖（Graph）是一種由頂點（Vertices）經由邊（Edges）連接而成的數學結構。
2. 圖的類型
並非所有的連接都是一樣的。根據我們試圖建立的模型，我們會使用不同類型的圖：
無向圖（Undirected Graphs）
在無向圖中，邊是沒有方向的。如果 A 人與 B 人之間有連接，那麼這種關係是雙向的。例子：Facebook 的好友關係。如果我是你的好友，你自然也是我的好友。
有向圖（Directed Graphs / Digraphs）
在有向圖中，邊帶有箭頭，表示特定的方向。例子：Twitter 或 Instagram 的追蹤關係。你追蹤某位名人，並不代表他們也會追蹤你！
加權圖（Weighted Graphs）
有時候，連接會帶有「代價」或「數值」，這稱為權重（Weight）。例子：在地圖上，兩個城市之間的邊可能有 50 的權重，代表距離 50 英里。
快速複習：
- 無向圖： 雙向道。
- 有向圖： 單行道。
- 加權圖： 需要付過路費或具有特定距離的道路。
3. 電腦如何儲存圖
電腦無法「看到」圖的繪圖，所以我們必須以電腦能理解的方式儲存數據。主要有兩種方法：
方法 A：鄰接矩陣（Adjacency Matrix）
這是一個二維表格（或網格），行與列代表頂點。如果有邊連接，我們就在對應儲存格填入 1，若沒有則填入 0。如果是加權圖，我們則儲存權重（Weight），而不是 1。
優點： 檢查兩個節點之間是否存在特定連接非常快速。
缺點： 如果節點很多但連接很少（這種圖稱為稀疏圖），會浪費大量記憶體。
方法 B：鄰接串列（Adjacency List）
這就像一本通訊錄。每個頂點都有一個列表，記錄了它直接連接的所有其他頂點。
例子：節點 A: [B, C], 節點 B: [A], 節點 C: [A]。
優點： 對於稀疏圖來說，節省記憶體空間。
缺點： 檢查兩個特定節點是否相連可能會較慢，因為你必須在列表中進行搜尋。
常見錯誤提醒：
學生常忘記在無向圖中，A 與 B 之間的邊必須在矩陣中記錄兩次（在 A 行 B 列，以及 B 行 A 列各記錄一次），因為路徑是雙向的！
關鍵重點：
對於「稠密圖」（大量連接）使用鄰接矩陣，對於「稀疏圖」（少量連接）使用鄰接串列。
4. 圖的遍歷（Traversing a Graph）
「遍歷」簡單來說就是依照特定順序訪問圖中的節點。你需要掌握兩種主要方法：
深度優先搜尋（Depth-First Search, DFS）
核心概念： 沿著一條路徑盡可能深入，直到無法繼續，然後回溯並嘗試另一條路徑。想像探索迷宮時，沿著左邊牆壁一直走，直到遇到死胡同為止。
- 記憶技巧： DFS 使用堆疊（Stack）（後進先出，LIFO）。
- 類比： 就像一個人在漆黑的洞穴中探索，順著一條隧道走到盡頭，再返回上一個交叉路口。
廣度優先搜尋（Breadth-First Search, BFS）
核心概念： 先查看所有直接相鄰的節點，然後再查看它們的鄰居。它是以「層級」向外擴展的。
- 記憶技巧： BFS 使用佇列（Queue）（先進先出，FIFO）。想像商店裡的「排隊」，先來先服務。
- 類比： 就像水面上的漣漪，從丟入石子的中心點向外擴散。
BFS 的步驟：
1. 選擇一個起始節點並將其加入佇列（Queue）。
2. 將其標記為「已訪問」。
3. 當佇列不為空時：
a. 移除佇列最前端的節點。
b. 查看該節點所有未訪問的鄰居。
c. 將這些鄰居加入佇列並標記為「已訪問」。
你知道嗎？
Google 地圖經常使用這些演算法的變體來計算你家與你最愛披薩店之間的最短路徑！
5. 總結清單
如果內容看起來很多，別擔心！這裡有一份考試前必備的「速查表」：
- 圖的組成： 頂點由邊連接。
- 方向： 無向（雙向）與 有向（單向）。
- 權重： 邊上的數值，代表成本或距離。
- 儲存： 矩陣（二維陣列）與 串列（鄰居列表）。
- DFS： 向深處探索；使用堆疊（Stack）。
- BFS： 向寬處（逐層）探索；使用佇列（Queue）。
加油：圖論是許多進階課題的基礎。一旦你掌握了矩陣與串列、堆疊與佇列的區別，你就已經攻克最難的部分了！