From my understanding, the general implementation of an adjacency list is using a hashtable with vertices as keys and linked lists to as values in the hashtable to represent the adjacent vertices of the key. It is also said that the time complexity of finding all the neighbours of a given vertex in the graph using the adjacency list if O(1), as you simply look up the vertex in the hashtable. However, doesn't a hashtable look up have worst case O(n) time? So it shouldn't be constant time? Any help would be much appreciated.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Usually vertices can be represented with consecutive integers, then you can just use an array instead of a hash table. If you insist on using a hash table have a look at perfect hashing
-
$\begingroup$ Thank you, can we, in theory, assume we have a perfect hash to obtain O(1) time? $\endgroup$ Feb 16 at 16:46
-
$\begingroup$ You can construct hash tables that use perfect hashing in linear expected time, so if that's good enough for you then yes. (As a consequence you can also construct them with high-probability in time $O(n \log n)$). $\endgroup$– StevenFeb 16 at 16:58