圖論中的哈希表

Question

我正在閱讀哈希表中的一篇文章。這是文本片段。

散列表對於任何圖論問題都很有用，其中節點 具有實數名稱而不是數字。這裏，當讀取輸入時，按照出現順序從1開始向頂點分配頂點。 同樣，輸入可能會有大量按字母順序排列的 條目。例如，頂點可以是計算機。然後，如果某個特定安裝將其計算機列爲ibm1，ibm2，ibm3，...，則將其計算機列爲ibm1，ibm2，ibm3，...。 。 。 ，如果使用搜索樹 ，可能會對效率產生顯着影響。

我上面的文字

1. quesitons是什麼意思作家「作爲輸入被讀取，verticies並將從1日起整數」不，我們計算輸入散列鍵讀？

2. 作者所說的「如果使用搜索樹，可能會對效率產生巨大影響」。

3. 與搜索樹相比，哈希表如何在圖論問題中有所幫助？

謝謝！

Answer 1

（1）這是一個不是集合的映射，當然它們會計算散列值，但節點映射到整數，這就是映射的目的。
（2）搜索樹是O（logn）搜索，使用基於搜索樹的映射會增加所有ops * O（logn）的時間複雜度。 [例如，由於查找時間的原因，BFS將採用O(logV*[V+E))而不是O(V+E)。 （3）哈希表是O（1），所以在平均情況下，哈希表的時間複雜度會更好。