Why Graph adjacency is not defined as adjacency set, but rather adjacency list?

Question

In Graph Theory, we know that an Vertex adjacencies can be represented using Adjacency list data structure. On contrary, adjacency set is not widely mentioned anywhere in the Graph Theory. Why is that so?

Here's the pros, i can think of.

1. As Set property, the graph could provide a guarantee in term of duplicated edge and many other properties of Set. Moreover all set operation from the Set Theory became available which is more intuitive to work with the analysis. Such as:

   • vertex_set_A | vertex_setB is the union operation.
   • vertex_set_A & vertex_set_B, is the intersection operation.

2. *Opinion, Set is more understandable as it has correlation in the mathematical proofing. It is also provide a good abstraction of how the low level code dealing with array and stuff.

3. In term of Performance, one could use HashSet implementation which would provide a constant time operation. Or TreeSet when the graph need to dynamically changed frequently on log time operation.
4. List data structure also maintain the ordering property of the element which serve no purpose in most graph. In fact, list iterates in ordered fashion which should not happened in the first place. Indexed Ordered should not matter and Set could provide that. The only time when ordering mattered is when the graph is weighted, and thus the ordering based on the weight, in which TreeSet operate mostly in log time operation.

So, I am unsure why most graph algorithms only mentioning adjacency list. Is it because of the technology barrier where Set is harder to implement, whereas List is easier?

Answer 1

This is indeed a very good question, the fact that there isn't a comprehensive answer yet just iterates the question one more time, 'why not' indeed.

The reasons in the comments to me seem more like make-do excuses in that this is just what has existed throughout history, still not enough to warrant an actual reason.

List is merely a general label and you could(and should) use sets if that's better suited to your task.

Some people would argue the set doesn't provide you a guaranteed O(1) lookup time - it's amortized and that the worst case is still O(n) even if very unlikely, others would reason faster iteration via lists, and then there's the argument about implementation feasibility.

While they're technically not wrong, I don't really buy into any of those being the primary reasons.
I feel the real reason is that they're used 'just because convention'.
The general label was 'list' and it was taken literally often enough to lose its genericness.

Certainly go ahead and use a set if your application lends itself to it.
My textbook used them too.

(Oh and an example to drive that home when I say 'application lending itself to it'; If you need to find indegrees very often in your application, the set will give you an O(V) runtime where V denotes number of vertices, adjacency list will give you O(E) runtime where E denotes number of edges. For dense graphs, O(E) tends to become O(V^2) assuming no parallel edges are allowed. Thus an adjacency set would give you a better runtime performance here.)