什麼類型的應用程序是每個數據結構用於存儲圖形的邊緣最適合？

Question

這是來自我正在進行的練習測試...不知道如何回答這個問題：

考慮在圖中存儲邊（鄰接矩陣，鄰接列表，邊列表）的三種數據結構。每種數據結構最適合哪種類型的應用程序？

糾正我，如果我錯了，但據我所知，鄰接矩陣是表示圖的效率最低的方法，因爲二維數組中的元素表示不存在的邊，而其他兩個數據結構只包含表示存在邊緣的元素，因此任何操作的遍歷速度都較慢。如果這是真的，那麼爲什麼有人想使用它？

對於鄰接列表，它比鄰接矩陣更有效，但仍包含冗餘信息 - >如果邊連接頂點i和j，則包含頂點i的頂點節點出現在頂點的鄰接列表中j並且同時包含頂點j的頂點節點出現在頂點i的鄰接列表中。

而...邊緣列表是最有效的。

因此，重申我的問題....如果一個邊界列表是最有效的表示，爲什麼你會想要使用其他兩個之一呢？

任何幫助，將不勝感激，謝謝。

Answer 1

你只是在談論空間效率問題。還有時間。如果您有頂點數字，矩陣只需要一條或幾條指令來查找邊緣值。你不能變得更快。實現和維護也非常簡單。 （不利的一面是，它需要O（n^2）來初始化，而不管邊數是多少，但是有一個解決方案。）其他形式都涉及某種搜索。即使您將鄰接列表作爲O（1）訪問的哈希值，時間常數因子遠遠高於矩陣。邊緣列表只有在處理邊緣時纔有意義，不需要根據頂點查找邊緣。