Skiena 的演算法設計手冊（第 3 版，第 204 頁）提到了鄰接表，而不是一般的鄰接表示，將它們定義為為每個頂點分配a一個L_a帶有底層集合的單鏈表set(L_a) = {b | (x, b) <- edges, x == a}。
我很驚訝 Skiena 將單鏈表作為實作集合的最終資料結構L_a。我的印象是，與陣列和哈希表相比，鏈表通常不受歡迎，因為：
- 它們對迭代不是快取友好的（就像陣列一樣），并且處理器速度和主記憶體訪問之間的差距變得更加重要。（例如Stroustrup 的這個視頻 (7m)。）
- 他們沒有帶來太多的好處，特別是當訂單不重要時。鏈表相對于陣列的優勢在于它們允許恒定時間添加和洗掉。但是在我們不關心順序的情況下，這些也可以是對陣列的恒定時間操作，使用“交換和彈出”進行洗掉。哈希表將具有恒定時間搜索的額外優勢。我的理解是哈希表比鏈表或陣列花費更多的記憶體，但這個考慮變得相對不那么重要。（也許在沒有特定應用程式的情況下，此宣告沒有意義。）
其他來源以不同的方式對待鄰接串列。例如，維基百科提出了一個實作，其中L_aare 陣列。而在斯通的演算法函式式編程的L_a是無序的集合，實作最終的方案串列（這反過來又使我感到奇怪）。
我的問題：是否有我遺漏的考慮因素，它使單鏈表在鄰接表示中具有顯著優勢？
我真誠地要求在您投票結束這個問題之前，或發表帶有無情語氣的評論之前，請先問問自己，這樣做是否真的在幫助本網站實作其目標。
uj5u.com熱心網友回復：
我認為在大多數實際用例中，單向鏈表作為鄰接表的默認表示沒有任何普遍的共識。
然而，單向鏈表幾乎是您可能擁有的鄰接表的最嚴格的實作，因此在一本關于“演算法設計”的書中，在這種表示中考慮鄰接表是有意義的，除非您需要一些特殊的東西它們，如隨機訪問、雙向迭代、二分搜索等。
當談到在顯式圖上的演算法的實際實作（大多數實作是在隱式圖上）時，我認為單向鏈表通常不是一個好的選擇。
我的首選鄰接串列圖表示是一對并行陣列：
- 頂點編號從 0 到 n-1
- 有一個邊陣列，其中包含按源頂點編號排序的所有邊。對于無向圖，每條邊在這里出現兩次。源頂點通常不需要存盤在這里。
- 有一個頂點陣列，它為每個頂點存盤其邊在邊陣列中的結束位置。
這是一個很好的、緊湊的、快取友好的表示，易于使用并且只需要兩次分配。
我通常可以找到一種簡單的方法來在線性時間內構建這樣的圖添加。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/387597.html
上一篇：通過字串值從無序映射中獲取列舉鍵
下一篇：海量資料的搜索策略