In answering this question, I was looking for references (textbooks, papers, or implementations) which represent a graph using a set (e.g. hashtable) for the adjacent vertices, rather than a list. That is, the graph is a map from vertex labels to sets of adjacent vertices:
graph: Map<V, Set<V>>
In fact, I thought that this representation was completely standard and commonly used, since it allows O(1) querying for an edge existence, O(1) edge deletion, and O(1) iterating over the elements of the adjacency set. I have always represented graphs this way both in my own implementations and teaching.
To my surprise, most algorithms textbooks do not cover this directly, and instead represent it using a list of labels:
graph: Map<V, List<V>>
As far as I understand, adjacency lists seem strictly worse: both representations support O(1) vertex additions and iteration over adjacent edges, but adjacency lists require O(m) for edge removal or edge existence (in the worst case).
Yet I am baffled that, for example Cormen Leiserson Rivest Stein: Introduction to Algorithms, Morin: Open Data Structures, and Wikipedia all suggest using adjacency lists. They mainly contrast adjacency lists with adjacency matrices, but the idea of storing adjacent elements as a set is only mentioned briefly in an off-hand comment as an alternative to the list representation, if at all. (For example, Morin mentions this on page 255, "What type of collection should be used to store each element of adj?") I must be missing something basic.
Q: What is the advantage of using a list instead of a set for adjacent vertices?
Is this a pedagogical choice, an aversion to hashmaps/hashsets, a historical accident, or something else?
This question is closely related, but asks about the representation
graph: Set<(V, V)>
. The top answer suggests using my representation. Looking for a bit more context on this.The second answer suggests hash collisions are a problem. But if hash sets are not preferred, another representation of maps and sets can be used, and we still get great performance for edge removal with a possible additional logarithmic factor in cost.
Bottom line: I don't understand why anyone would implement the edges as a list, unless all vertex degrees are expected to be small.
Set<(V, V)>
. Just different memory consumption and less direct (but still averageO(1)
) access. I guess it depends mostly on the sparsity of the graph (how many edges each node has on average) how well they perform in practice. $\endgroup$