owever, 64 bits for a pointer can be overkill. If you instead use 16bit integers as pointer offsets, we can fit up to 18 edges before breaking point.
= 300 / 16 = 18 d = ((18 * 300) / (300^2)) d < 1/16 aka 0.06 < 0.0625
Each of these examples ignore the overhead of the adjacency lists themselves (
64*2 for a vector and 64 bit pointers).
If you use a hash table instead of either adjacency matrix or list, you'll get better or same big-O run-time and space for all operations (checking for an edge is
O(1), getting all adjacent edges is
There's some constant factor overhead though for both run-time and space (hash table isn't as fast as linked list or array lookup, and takes a decent amount extra space to reduce collisions).
Just going to touch on overcoming the trade-off of regular adjacency list representation since other answers have covered other aspects.
It is possible to represent a graph in adjacency list with EdgeExists query in amortized constant time by taking advantage of Dictionary and HashSet data structures. The idea is to keep vertices in a dictionary and for each vertex we keep a hash set referencing to other vertices it has edges with.
One minor trade-off in this implementation is that it will have space complexity O(V + 2E) instead of O(V + E) as in regular adjacency list since edges are represented twice here (because each vertex have its own hash set of edges). But operations such as AddVertex, AddEdge, RemoveEdge can be done in amortized time O(1) with this implementation, except for RemoveVertex which takes O(V) like adjacency matrix. This would mean that other than implementation simplicity adjacency matrix don't have any specific advantage. We can save space on sparse graph with almost the same performance in this adjacency list implementation.
Take a look at implementations below in Github C# repository for details. Note that for weighted graph it uses a nested dictionary instead of dictionary-hash set combination so as to accommodate weight value. Similarly for directed graph there is separate hash sets for in & out edges.
Note: I believe using lazy deletion we can further optimize RemoveVertex operation to O(1) amortized even though I haven't tested that idea. For example upon deletion just mark the vertex as deleted in dictionary, and then lazily clear orphaned edges during other operations.