資料結構與演算法
像頂點約100萬個、邊約300萬條的道路網這樣，邊數相對於頂點數很少的（稀疏）圖，適合以下列何種方式存放在記憶體中？
- A鄰接矩陣。能以 O(1) 檢查兩個頂點之間是否有邊，記憶空間也最少
- B鄰接串列。記憶空間與頂點數加邊數的和成正比，適合依序走訪從某個頂點出發的邊
- C鄰接矩陣。記憶空間只與邊數成正比
查看答案與解析
正確答案：B. 鄰接串列。記憶空間與頂點數加邊數的和成正比，適合依序走訪從某個頂點出發的邊
鄰接矩陣對 V 個頂點使用 V×V 的表格，100萬個頂點需要10¹²個元素，即使每個元素1位元也約需125 GB。鄰接串列只列出與各頂點相連的頂點，因此記憶空間為 O(V + E)，這個例子只需數百萬筆左右。鄰接矩陣的優點是能以 O(1) 檢查邊是否存在，適合邊多的（稠密）圖或頂點少的圖。對於像廣度優先搜尋或戴克斯特拉演算法這樣依序走訪從頂點出發之邊的處理，鄰接串列的效率較好。
- A. 能以 O(1) 檢查邊是否存在是正確的，但記憶空間與頂點數的平方成正比，對稀疏圖是很大的浪費。
- B. 正確。記憶空間只需 O(V + E)，也適合依序走訪相鄰頂點的處理。
- C. 鄰接矩陣的大小與邊數無關，是頂點數的平方。