與列表相比，哪些算法在鄰接矩陣中表現更好？

是否有任何算法的鄰接矩陣優於鄰接列表？反之亦然呢？與列表相比，哪些算法在鄰接矩陣中表現更好？

2011-05-31 Karthick

就運行時間而言，鄰接矩陣幾乎總是優於列表。 List實現將使用更少的內存（與邊的數量成比例）來存儲圖。

因此，如果內存確實很重要（它肯定會對具有大量節點的稀疏圖），請使用列表。如果運行時間很重要，並且圖表可能很密集，請使用鄰接矩陣。

2011-05-31 07:07:50

嗨，謝謝。在運行時間方面，列表是否比矩陣優於矩陣？ [自從你說*幾乎*] – Karthick 2011-05-31 07:12:42

只有在使用密集矩陣（即二維數組）的情況下才會記住命中。如果你使用稀疏矩陣，那麼你也可以節省空間，但是你必須小心如何矩陣遍歷。但是由於緩存的影響，2D數組也是如此。 – Adam 2011-05-31 07:12:51

@Karthick，當使用密集矩陣時，一個算法找到頂點的程度會比列表更快。整個矩陣列/行必須遍歷，而列表只遍歷現有邊。再次，稀疏矩陣解決了這個問題。 – Adam 2011-05-31 07:15:31

回答