圖庫實現

我正試圖實現一個加權圖。我知道有兩種方法來實現加權圖。可以使用二維數組（鄰接矩陣），也可以使用鏈表（鄰接列表）。哪一個更高效，更快？圖庫實現

2012-05-09 Rontogiannis Aristofanis

兩者中哪一個更高效，更快？

這取決於您的使用情況以及要存儲的圖表種類。

設n是節點的數量，m是邊的數量。如果您想知道兩個節點u和v是否連接（以及邊的權重），則只需通過檢索條目A[u,v]即可在相鄰矩陣的恆定時間內（在O-notation，O（1））確定此值。在鄰接列表中，您必須查看u列表中的每個條目，或v的列表 - 最壞的情況下，可能有n個條目。因此，鄰接列表的邊緣查找在O（n）中。

鄰接矩陣的主要缺點是需要的內存。總而言之，您需要存儲n^2個條目。使用鄰接列表時，只需要存儲實際存在的邊（m個條目，如有向圖）。所以如果你的圖很稀疏，鄰接列表顯然會佔用更少的內存。

我的結論是：如果您的主要操作是檢索兩個特定節點的邊權重，則使用鄰接矩陣;在圖表足夠小的條件下，以便n^2個條目適合內存。否則，請使用鄰接列表。

來源

2012-05-10 08:46:45 clstaudt

非常好的答案。非常感謝你。 –

就我個人而言，我會去鏈接列表方法，假設它通常是一個稀疏圖（即大多數數組單元是浪費空間）。

去維基百科閱讀adjacency lists（自從我使用圖表以來已經過了很長時間），並且在兩種方法之間的權衡方面有一個很好的部分。最終，與許多/或選擇一樣，它將歸結爲「取決於」，這取決於圖書館可能的用例。

讀取wiki文章後，我認爲有利於使用列表的另一點是附加數據到每個向線段（或甚至不同的權重，2點之間等認爲步行/自行車/車距離的）

來源

2012-05-09 18:58:25 Alok

回答

相關問題