圖形鄰接表如何實現節點/頂點的O（1）查找。陣列？

我閱讀了使用「鄰接列表」實現的圖形的規範，即在不變的時間內添加邊。但是這需要使用O（1）進行節點查找。我想要儘可能好的表現。這裏的問題是哪個數據類型會給我這個問題。已經考慮了散列表，最壞的情況是散列表仍然是O（n）。圖形鄰接表如何實現節點/頂點的O（1）查找。陣列？

我可以用這個數組嗎？該節點可以是任何數據類型，泛型。這可以通過一些基於節點的散列函數生成索引值來完成嗎？那會給我O（1）。當然，我可以大寫並使用LinkedList和indexOf。持續時間最好。

2009-11-18 Algific

假設你有一個好的散列，通常假定HashMap有O（1）運行時，特別是對於作業目的。 – notnoop 2009-11-18 21:54:04

我問我的小組組長，一個博士研究生。 O（1）預計運行時間，我需要分析的是最壞的情況。 – Algific 2009-11-19 09:07:10

任何使用哈希算法的步驟都會產生碰撞風險，所以最壞的情況（不太可能）是歐米茄（N）。

使用列表時，同時插入和檢索的最佳保證漸近性能爲O（log N）。如果您將節點存儲爲堆或平衡樹之類的東西，就會得到這個結果。你不能在兩個操作上做得更好，因爲它會讓你違反排序時可證明的O（N log N）。

2009-11-23 23:56:08 Eric

一般而言，絕對是。只要輸入集合是有限的並且已知的，完美的哈希可以完全避免碰撞。 – 2010-09-29 01:27:27

回答