O（1）鄰接列表使用HashSet查找時間？

在我的算法類中，我被告知圖表表示的鄰接表的縮小是O（n）查找時間，用於遍歷每個節點對應的相鄰節點的數組。我通過使用將節點映射到其相鄰節點的HashSet的HashMap來實現鄰接列表，是不是隻需要O（1）查找時間？有什麼我失蹤？O（1）鄰接列表使用HashSet查找時間？

來源

2017-03-26 discuit

正如你所知，在HashMap中使用鍵查找值是O（1）。但是，在鄰接列表中，HashMap的值也是其相鄰節點的列表。鄰接表的主要目的是迭代相鄰節點。例如：圖形遍歷算法，如DFS和BFS。在你的情況下HashSet。假設HashSet中的元素數量是n。然後，即使在HashSet中迭代所有元素也是O（n）。

So, total complexity would be O(1)+O(n). 

    Where O(1)= look up in HashMap 
      O(n)= iterate all the elements

一般來說，鄰接表對於稀疏圖是比較好的，因爲它是隻有少量邊的圖。這意味着每個節點（HashMap的關鍵字）中相鄰元素的數量較少。所以查找元素不會花費更多。

來源

2017-03-26 03:43:21

我不確定我清楚我的意思是HashSet。我的意思是我使用HashSet數據結構（基本上是一組O（1）查找時間的元素）作爲我的密鑰的值。如果我是正確的，你認爲我的價值是我命名HashSet的通用列表。 – discuit

好吧，我的意思是說，鄰接表的主要目的是存儲鄰接節點，並且每當這些節點需要像DFS這樣的算法時，它們就會使用並遍歷所有節點。所以如果你使用HashSet，迭代的時間複雜度也是O（n）。並且查找HashSet是O（1）。你是對的。看到我更新的答案。我認爲現在很清楚。 –

我通過使用節點映射到一個哈希一套自己的相鄰節點的一個HashMap實現我鄰接名單，那不是隻需要O（1）查找時間？ [重點煤礦]

右—但「adjacency list」通常意味着表示數組或一個鏈接列表，而不是一個HashSet：換句話說，鄰接表被用於遍歷頂點的鄰居，而優化而不是查詢兩個頂點是否是鄰居。

來源

2017-03-26 04:19:46 ruakh

O（1）鄰接列表使用HashSet查找時間？

回答

相關問題