1什麼是圖論
生活中有很多東西不是「一條線排下去」的，而是「彼此互相連接」的關係：朋友之間的社交網路、捷運站之間的路線、電腦之間的網路連線、城市之間的道路。這種「一堆東西＋它們之間的連接關係」，在資訊科學裡就叫做圖（Graph）。
圖由兩種東西組成：節點（Node／頂點）——圖裡的每一個「東西」本身，例如一台裝置、一個人、一個路口；邊（Edge／連線）——兩個節點之間的一條連接關係，例如「裝置A跟裝置B有連線」。
圖論是你目前為止學過最貼近「真實世界關係」的資料結構主題——之前的清單是「一串排好順序的資料」，圖是「資料之間彼此的連接關係」，兩者要問的問題完全不同：清單問「第幾個是什麼」，圖問「這個東西跟那個東西連不連得起來、要繞幾步才到得了」。
🆕 補充圖解：4個節點A、B、C、D兩兩之間有連線（度數都是3），E是孤立節點（度數0，紅色）新增
2核心概念，依課程題目的順序拆解
1
圖的基本組成——節點與連線
一個網路有 N 個設備（節點）與 M 條連線（邊）。這是整個單元最基本的資料格式：先確定「有幾個節點」，再確定「哪些節點之間有連線」。
網路連線數（GRAPH01-001）——單純讀懂輸入格式、輸出連線數 M
2
節點的「連線數」（degree，度數）
你要做的事：給定一個節點 X，計算 X 連到了幾個其他節點。這是圖論裡最基本的統計量，叫做「度數」——你不用知道這個英文名詞，但一定要理解「算某個節點連了幾條線」這個動作，因為後面「找連線最多的設備」「孤立設備」都是從這個概念延伸出來的。
指定設備連線數（GRAPH01-002）
⚠️ 常見誤區
漏算——每一條連線會同時牽涉兩個節點，檢查連線清單時，要記得同一個節點可能出現在「起點欄位」也可能出現在「終點欄位」，兩邊都要算進去。3
判斷兩個節點是否直接相連
你要做的事：給定兩個節點 X、Y，判斷它們之間有沒有一條連線直接連著。這是「圖的查詢」最基礎的一種——之後「兩段路可到達」會在這個基礎上多繞一步。
是否直接相連（GRAPH01-003）
4
完整網路——所有節點兩兩都相連
若 N 個節點中，每兩個不同節點都直接相連，稱為完整網路。你可以推導出：N 個節點兩兩配對的組合數，就是完整網路需要的連線數（例如3個節點兩兩配對，共有3種配對方式）。這一題要你算的是「距離完整網路還缺幾條線」——先算出完整網路需要的連線數，再減掉目前已有的 M。
完整網路缺幾條線（GRAPH01-007）
5
綜合分類——把前面的概念組合起來判斷
若連線數 M 為 0，代表所有節點都沒連線（EMPTY）；若 M 剛好等於完整網路需要的連線數，代表所有節點兩兩都連了（FULL）；其他情況輸出 NORMAL。這一題沒有新概念，重點是練習把「概念4的完整網路連線數計算」拿來跟目前的 M 比較，寫出正確的判斷順序。
網路狀態分類（GRAPH01-008）
6
找出連線數最多／最少（0條）的節點
你要做的事：
- 找連線數最多的設備（若有多個並列，輸出編號最小者）——概念2套用在「每一個節點」身上，再從中找最大值，跟你在M0/M1學過的「找最大值＋記錄位置」是同一個套路
- 孤立設備（沒有任何連線的節點，也就是連線數=0的節點）——統計有幾個節點的連線數是0
找連線最多的設備（GRAPH01-004）孤立設備數量（GRAPH01-005）
7
兩段路可到達——圖論真正的核心，「走路徑」
你要做的事：判斷 X 能不能透過一個中繼節點走兩段路到達 Y（如果 X 和 Y 直接相連，不算兩段路）。這是這個單元第一次真正要你「沿著連線走」，而不只是統計連線數量——你需要檢查：是否存在某個節點 Z，同時跟 X 相連、也跟 Y 相連。
🆕 補充圖解新增
兩段路可到達（GRAPH01-006）
⚠️ 常見誤區
忘記排除「X和Y直接相連」的情況——題目明確說直接相連不算兩段路，這是容易漏掉的邊界條件。8
連通群組——把整張圖分成好幾群
你要做的事：計算整個網路總共分成幾個「連通群組」——同一群組內的裝置都能透過連線（可能要繞好幾步）互相到達；不同群組之間完全沒有連線路徑，就算繞再多步也到不了。這是圖論進階最重要的新概念：不再只看「一步」或「兩步」，而是「不管繞多少步，到得了就算同一群」。
訊號網路的連通群組數（JSG01-009）
⚠️ 常見誤區
只看有沒有「直接」連線，忘記兩個節點即使沒有直接連線，只要能透過中間的節點（不管幾個）繞過去，就算同一個連通群組。9
樹狀結構——上下游關係與到根節點的距離
有一類題目給的不是「任意連線」，而是每個節點指定「上游接收站編號」（例如「量子訊號的接力傳輸」「訊號站到主機的轉傳距離查詢」）——這種「每個節點只有一個上游」的圖，叫做樹（Tree），是圖的一種特殊型態。這一類題目常問的是「從某個節點沿著上游關係一路往上走，要走幾步才會到主機／根節點」。做法是沿著上游指標一直往上跳，同時計算跳了幾步，直到跳到「上游編號為0」（代表已經到主機）為止。
量子訊號的接力傳輸（W0-03）訊號站到主機的轉傳距離查詢（JSG01-010）
10
更多進階應用（可依需要挑戰）
圖論進階還有幾題結合了其他情境包裝相同的核心技巧——「山區備援工程」（樹狀結構＋連線長度）、「基地台訊號覆蓋」（二維地圖上的圖論）、「社團聯絡網(6-4)」（連通群組的應用）。這些題目沒有新概念，是概念8、9的實戰演練，建議前面的概念都熟悉之後再挑戰。
3建議練習順序對照表
| 順序 | 概念 | 題目 | 課程 |
|---|---|---|---|
| 1 | 圖的基本組成 | 網路連線數（GRAPH01-001） | M2-07 |
| 2 | 節點連線數（度數） | 指定設備連線數（GRAPH01-002） | M2-07 |
| 3 | 直接相連判斷 | 是否直接相連（GRAPH01-003） | M2-07 |
| 4 | 完整網路 | 完整網路缺幾條線（GRAPH01-007） | M2-07 |
| 5 | 綜合分類 | 網路狀態分類（GRAPH01-008） | M2-07 |
| 6 | 找最多/最少連線 | 找連線最多的設備／孤立設備數量 | M2-07 |
| 7 | 兩段路徑 | 兩段路可到達（GRAPH01-006） | M2-07 |
| 8 | 連通群組 | 訊號網路的連通群組數（JSG01-009） | M2-08 |
| 9 | 樹狀結構與到根距離 | 量子訊號的接力傳輸／訊號站到主機的轉傳距離查詢 | M2-08 |
| 10 | 進階應用 | 山區備援工程／基地台訊號覆蓋／社團聯絡網 | M2-08 |
🆕 本頁新增內容說明
以下視覺元素為 Cowork 潤飾時新增，MD 正本中沒有：① 節點連線SVG示意圖（含孤立節點）② 兩段路徑SVG示意圖。若確認保留，建議之後補進 MD 正本。