使用相鄰矩陣（Adjacency matrix）記錄一個有V 個點E 個邊的無向圖之空間複雜度為何？

題目

使用相鄰矩陣（Adjacency matrix）記錄一個有V 個點E 個邊的無向圖之空間複雜度為何？ A. O(VE) B. O(V2) C. O(E) D. O(V+E)

官方答案

• 答案：B. O(V2)

解析

相鄰矩陣（Adjacency matrix）以 V×V 的二維陣列記錄 V 個頂點兩兩之間是否有邊，無向圖中 matrix[i][j]=matrix[j][i]，所需空間恆為 V² 個儲存格，與邊數 E 無關，故空間複雜度為 O(V²)，選 B。選項 D 的 O(V+E) 是相鄰串列（Adjacency list）的空間複雜度；A 的 O(VE) 與 C 的 O(E) 皆不符合矩陣表示法。觀念重點：矩陣法適合稠密圖，無論邊多寡都固定佔用 V² 空間；稀疏圖應改用串列以節省空間。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。