Learning Objectives
- 說出圖的基本術語：節點、邊、有向與無向、權重、度數
- 用鄰接矩陣與鄰接串列表示一張圖，比較兩者的空間與查詢成本
- 追蹤 BFS 的佇列、visited、dist、parent 在每一步怎麼變
- 說明 BFS 為什麼能找到無權重圖的最短路徑，並用 parent 還原路徑
- 把方格迷宮看成圖來做 BFS，並用 BFS 數出連通元件的個數
東西和東西之間的關係
捷運路線圖上，站和站之間有軌道相連；社群網站上，人和人之間有好友關係；網頁和網頁之間有超連結。 這些資料的重點不在「一排資料」，而在誰和誰相連。描述這種關係的資料結構叫做圖（graph）。
有了圖，很多問題就有了共同的解法：
- 從台北車站到動物園，最少要搭幾站？
- 你和某位同學之間，隔了幾層朋友？
- 迷宮從入口走到出口，最少要走幾步？
這一課先學怎麼把圖存進程式，再學廣度優先搜尋（BFS，breadth-first search）：從起點開始一層一層往外擴散，能算出「最少要走幾步」。
圖的術語
一張圖由兩種東西組成：
| 術語 | 意思 | 例子 |
|---|---|---|
| 節點（node，也叫頂點 vertex） | 圖裡的「東西」 | 捷運站、使用者、網頁 |
| 邊（edge） | 兩個節點之間的關係 | 兩站之間的軌道、好友關係 |
| 無向圖（undirected） | 邊沒有方向，A 連到 B 就表示 B 也連到 A | 臉書好友 |
| 有向圖（directed） | 邊有方向，A → B 不代表 B → A | IG 追蹤、網頁連結、課程先修 |
| 權重（weight） | 邊上的數字，例如距離、時間、票價 | 兩站之間 4 分鐘 |
| 度數（degree） | 一個節點連著幾條邊；有向圖分成入度（指進來）和出度（指出去） | 好友人數 |
| 路徑（path） | 沿著邊從一個節點走到另一個節點經過的節點序列 | 0 → 1 → 3 |
節點的個數通常寫成 V（vertex），邊的條數寫成 E（edge）。分析圖演算法時，複雜度會同時用到這兩個數，例如 O(V + E)。
這一課的圖都沒有權重（或者說每條邊的權重都是 1），「最短」就是「經過的邊最少」。有權重的最短路徑留到第 18 課。
把一張圖存進程式
程式讀進 5 條邊，同時建出兩種表示法。看右邊的矩陣：每讀一條邊會填兩格（m[u][v] 和 m[v][u]），所以無向圖的矩陣左右對稱。下面的鄰接串列每讀一條邊，兩端的串列各多一個鄰居。
鄰接矩陣與鄰接串列怎麼選
兩種表示法存的是同一張圖，差別在空間和各種操作的速度（V 是節點數、E 是邊數、deg(u) 是 u 的度數）：
| 鄰接矩陣 | 鄰接串列 | |
|---|---|---|
| 空間 | V × V 格，O(V²) | 每條邊記兩次，O(V + E) |
| u 和 v 之間有沒有邊？ | 看一格，O(1) | 掃過 u 的鄰居，O(deg(u)) |
| 列出 u 的所有鄰居 | 掃過整列，O(V) | 直接走訪串列，O(deg(u)) |
| 加一條邊 | O(1) | O(1)（加在串列尾端） |
實際的圖大多是稀疏（sparse）的：每個節點只連著少數幾個節點。例如一百萬個使用者、每人平均 200 個好友， 鄰接矩陣要一兆（10¹²）格，幾乎全是 0；鄰接串列只要存約兩億筆鄰居。所以圖演算法通常用鄰接串列， 只有節點很少、或邊非常密（稠密，dense）的圖才用鄰接矩陣。
三種語言常見的寫法：
adj = [[] for _ in range(n)] # Python：串列的串列
vector<vector<int>> adj(n); // C++：vector 的 vector
ArrayList<ArrayList<Integer>> adj = new ArrayList<>(); // Java：先放 n 個空的 ArrayList
圖不會變動時，Java 也常直接寫成 int[][] adj，接下來的範例就是這樣。
想一想：表示法與度數
下面的程式統計每個節點的度數，會印出什麼？
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4)]
deg = [0] * 5
for u, v in edges:
deg[u] += 1
deg[v] += 1
print(deg)
一張圖有 10,000 個節點，每個節點平均只有 4 個鄰居。用鄰接矩陣存，要幾格？
程式要非常頻繁地問「u 和 v 之間有沒有邊？」，而且圖只有 50 個節點。哪一種表示法最適合？
廣度優先搜尋：一層一層往外
把一顆石頭丟進水池，水波會一圈一圈往外擴散。BFS 就是這樣走一張圖：
- 先拜訪起點（第 0 層）
- 再拜訪起點的所有鄰居（第 1 層，距離 1）
- 再拜訪「第 1 層的鄰居裡，還沒拜訪過的」（第 2 層，距離 2）
- 一直到沒有新的節點為止
要做到「先處理完近的，再處理遠的」，需要第 10 課的佇列（queue）：先放進去的先出來。 新發現的節點排到佇列尾端，所以距離 1 的節點全部處理完之前，距離 2 的節點都還在後面排隊。
程式用三個陣列記錄狀態：
| 陣列 | 意思 | 一開始 |
|---|---|---|
visited[v] |
v 是否已經被發現（放進過佇列） | 全部 false，只有起點 true |
dist[v] |
從起點到 v 最少要走幾條邊 | 全部 -1（還沒走到），起點是 0 |
parent[v] |
v 是從哪個節點走過來的 | 全部 -1 |
注意標記 visited 的時機：放進佇列的時候就標記，而不是取出來的時候。否則同一個節點可能被好幾個鄰居重複放進佇列。
BFS：佇列、visited、dist、parent
藍色是正在處理的節點 u，黃色是還在佇列裡排隊的節點，淺綠色是已經拜訪過的節點。節點上方的紅字是 dist（∞ 表示還沒走到），綠色的邊是 parent 連成的樹。注意 dist 一定是先出現一堆 1、再出現 2、再出現 3：BFS 永遠先處理完同一層。
為什麼 BFS 找到的是最短路徑
在沒有權重的圖裡，BFS 第一次發現節點 v 的時候，dist[v] 就是起點到 v 的最少邊數。理由是：
- 佇列裡的節點，dist 永遠是「前面一段是 d、後面一段是 d + 1」，不會亂序
- 所以 BFS 一定先處理完所有距離 d 的節點，才開始處理距離 d + 1 的節點
- v 第一次被發現時，是被某個距離 d 的節點發現的；如果有更短的路，v 早就會被距離更小的節點先發現
parent 記下每個節點「第一次是從哪裡被發現的」。所有 parent 關係合起來是一棵BFS 樹（上面動畫裡的綠色邊）：
從任何節點沿著 parent 往回走，就會走回起點，而且走的正是一條最短路徑。
時間複雜度：每個節點最多進出佇列一次，O(V)；每個節點的鄰居串列都被掃過一次，無向圖的鄰居總數是 2E。 合起來是 O(V + E)。如果用鄰接矩陣，找鄰居要掃整列，會變成 O(V²)。
沿著 parent 還原路徑
這次把 BFS 寫成函式，回傳 parent。回到主程式後，從終點 6 開始，一直往 parent 走，直到 -1（起點沒有 parent）。收集到的順序是「終點到起點」，最後倒過來就是答案。
方格迷宮也是一張圖
很多問題沒有明說「圖」，其實也是圖。迷宮就是一個例子：
- 每個能走的格子是一個節點，用 (列, 行) 表示
- 上下左右相鄰、而且都能走的兩格之間有一條邊
- 牆（
#）不是節點
不需要先把鄰接串列建出來：走到格子 (r, c) 時，鄰居就是 (r-1, c)、(r+1, c)、(r, c-1)、(r, c+1)，
只要檢查有沒有超出邊界、是不是牆、走過了沒。常見的寫法是用兩個陣列 dr、dc 存四個方向的位移，用一個迴圈試四次。
dist 改成二維陣列，-1 一樣表示還沒走到，同時兼任 visited 的角色。佇列裡放的是座標：
Python 用 tuple (r, c)、C++ 用 pair<int, int>、Java 用 int[]{r, c}。
迷宮：從左上走到右下最少幾步
右邊的 dist 表會從左上角的 0 開始，一圈一圈長出 1、2、3。走到死路的格子（例如右上的 (1, 3)）也會被填上距離，因為 BFS 不知道哪條路通往終點，它會把所有走得到的格子都走一遍。
連通元件：圖分成幾塊
一張無向圖不一定整張連在一起。彼此走得到的節點合起來叫一個連通元件（connected component）。 例如社群網站上，兩群完全沒有共同朋友的人，就分屬不同的元件。
數元件的方法：從每個還沒拜訪過的節點開始做一次 BFS，這次 BFS 走得到的節點全部屬於同一個元件；做了幾次 BFS，就有幾個元件。
所有 BFS 加起來，每個節點和每條邊仍然只處理一次，總共還是 O(V + E)。
數連通元件
外層迴圈的 s 從 0 掃到 7。遇到還沒拜訪過的節點，就從它開始做一次 BFS，把走到的節點都標成同一個元件編號。注意 s = 1、2 時直接跳過，因為它們在第一次 BFS 已經被走到了。
想一想：BFS 的順序與成本
用上面 BFS 範例的同一張圖，改從節點 6 開始，拜訪順序是什麼？
adj = [[1, 2], [0, 3], [0, 3, 4], [1, 2, 5], [2, 5], [3, 4, 6], [5]]
如果把 visited[v] = True 從「放進佇列時」改到「從佇列取出時」才標記，會發生什麼事？
用鄰接串列做 BFS，V 個節點、E 條邊，時間複雜度是多少？
實作：隔了幾層朋友
adj 是 8 個人的好友關係（無向圖）。請完成 BFS，算出每個人和 0 號之間隔了幾層朋友，再印出距離 1～4 各有幾個人，以及從 0 號完全走不到的人數。這裡用 dist[v] == -1 兼任 visited。
重點整理
- 圖由節點和邊組成；邊可以有方向（有向圖）、可以有權重；度數是一個節點連著幾條邊
- 鄰接矩陣用 O(V²) 空間，查「有沒有邊」是 O(1)；鄰接串列用 O(V + E) 空間，列出鄰居很快，實際的稀疏圖大多用它
- BFS 用佇列一層一層往外走；放進佇列時就標記 visited；
dist[v] = dist[u] + 1、parent[v] = u - 在沒有權重的圖裡，BFS 算出的 dist 就是最少邊數；沿著 parent 往回走再倒過來，就是一條最短路徑
- 方格迷宮的每一格是節點，上下左右是邊；從每個沒拜訪過的節點各做一次 BFS，就能數出連通元件
- BFS 的時間複雜度是 O(V + E)
下一課：深度優先搜尋（DFS）。它不是一層一層走，而是一路往深處走到底再回頭，可以用來偵測環和安排先修順序。