下列相鄰矩陣（adjacency matrix）所表示的無向圖（undirected graph）中，共有多少個連通單元（connected component）？
A1正確答案
B2
C3
D4
答案與詳解
A
正確答案
無向圖連通單元數量判斷：觀察相鄰矩陣對稱性與非零元素分佈，確認所有節點是否可互相到達。
為什麼答案是 A
正確。將矩陣轉化為圖形後可發現：節點1-2-4-6-3-5形成一條貫穿所有節點的路徑（1↔2, 2↔4, 4↔6, 6↔3, 6↔5），故整個圖為單一連通單元。
載入中…
完整詳解
Pro · 無限重點 無向圖連通單元數量判斷：觀察相鄰矩陣對稱性與非零元素分佈，確認所有節點是否可互相到達。
秒殺技巧
畫出6個節點的連線圖或檢查矩陣幂次，若任兩點間皆有路徑則連通單元為1。本題矩陣顯示全圖連通。逐選項分析
A✓ 正確
正確。將矩陣轉化為圖形後可發現：節點1-2-4-6-3-5形成一條貫穿所有節點的路徑（1↔2, 2↔4, 4↔6, 6↔3, 6↔5），故整個圖為單一連通單元。
B✕ 陷阱
錯誤。可能誤判節點3或5為孤立群體，但實際上節點3透過6連接、節點5也直接連6，並未形成獨立子圖。
C✕ 陷阱
錯誤。可能將矩陣中零較多的區域誤認為分隔區塊，但未考慮間接路徑（如3→6→5）仍可連通。
D✕
錯誤。此選項對應多個完全分離的子圖，但本題矩陣明顯存在跨區連結，不可能有4個連通單元。
連通單元判斷要點
| 判斷方法 | 適用情境 | 注意事項 | 計算複雜度 |
|---|---|---|---|
| 視覺化繪圖 | 節點數≤10 | 注意對稱性與自環 | O(n²) |
| 矩陣幂次法 | 理論分析 | Aᵏ[i][j]>0表k步內可達 | O(n³logk) |
| DFS/BFS遍歷 | 程式實作 | 需標記已訪問節點 | O(V+E) |
| Union-Find | 動態連通性 | 適合邊逐步加入場景 | O(Eα(V)) |
陷阱提醒
相鄰矩陣中零元素集中易讓人誤以為圖不連通，但無向圖只需單一路徑即可連通。務必驗證間接連結（如節點3雖未直連1,2,4,5，但經6可達全部）。