圖形內存實現

Question

常用於在內存中表示圖形的兩種方法是使用鄰接列表或鄰接矩陣。使用指向鏈接列表的指針數組實現鄰接列表。是否有任何理由比使用矢量矢量更快？我覺得它應該使搜索和遍歷更快，因爲回溯會更簡單。

Answer 1

鏈接相鄰的向量是一個最喜歡的教科書meme與實踐中的許多變化。當然你可以使用矢量向量。有什麼區別？

其中之一就是鏈接（無論如何都是雙重鏈接）允許在常量時間內容易地添加和刪除邊緣。這顯然是重要的，只有邊緣集縮小和增長。對於邊緣矢量，任何單獨的操作都可能需要O（k），其中k是入射邊緣計數。

注意：如果鄰接列表中的邊緣的命令對您的應用程序不重要，您可以很容易地獲取帶有向量的O（1）刪除。只需將最後一個元素複製到要刪除的元素的位置，然後刪除最後一個！唉，有很多情況下（比如你擔心嵌入飛機的時候），當鄰接點的順序很重要時。

即使必須維護訂單，您也可以安排複製成本以分攤到平均值O（1），以便在許多操作中執行每次操作。在某些應用中，這還不夠好，只有當標記刪除的數量是矢量的一個固定分數時，才需要「刪除」標記（保留的頂點編號就足夠了），並進行壓縮。代碼非常繁瑣，在所有操作中檢查已刪除的節點會增加開銷。

另一個區別是開銷空間。鄰接列表節點非常小：只是一個節點號。雙鏈接可能需要4倍的數字空間（如果數字是32位，並且兩個指針都是64）。對於一個非常大的圖，400％的空間開銷不太好。

最後，長時間頻繁編輯的鏈接數據結構可能很容易導致高度不連續的內存訪問。與通過向量的線性訪問相比，這會降低緩存性能。所以這裏矢量勝利。

在大多數應用中，差異不值得擔心。再次，巨大的圖是現代世界的方式。

正如其他人所說的那樣，爲鄰接點使用一個廣義列表容器是一個好主意，它可以快速實現或者鏈接節點或節點向量。例如。在Java中，您可以使用List並使用LinkedList和ArrayList來實現/配置文件，以查看哪種最適合您的應用程序。 NB ArrayList壓縮每個remove上的陣列。如上所述，並無攤銷，儘管add s 爲攤銷。

還有其他的變化：假設你有一個非常密集的圖，那裏經常需要搜索所有出現在給定節點的邊，以找出具有特定標籤的邊。那麼你想要地圖的鄰接關係，其中的關鍵是邊緣標籤。當然，地圖可以是哈希或樹木或跳過列表或任何你喜歡的東西。

這個名單還在繼續。如何實現高效頂點刪除？正如您所預料的那樣，這裏也有其他選擇，各有優缺點。