d-Warshall for example. We have to use an adjacency matrix, or the algorithm will be asymptotically slower.
Or what if it's a dense graph on 30,000 vertices? Then an adjacency matrix might make sense, as you'll be storing 1 bit per pair of vertices, rather than the 16 bits per edge (the minimum that you would need for an adjacency list): that's 107 MB, rather than 1.7 GB.
But for algorithms like DFS, BFS (and those that use it, like Edmonds-Karp), Priority-first search (Dijkstra, Prim, A*), etc., an adjacency list is as good as a matrix. Well, a matrix might have a slight edge when the graph is dense, but only by an unremarkable constant factor. (How much? It's a matter of experimenting.)
Depending on the Adjacency Matrix implementation the 'n' of the graph should be known earlier for an efficient implementation. If the graph is too dynamic and requires expansion of the matrix every now and then that can also be counted as a downside?
To add to keyser5053's answer about memory usage.
For any directed graph, an adjacency matrix (at 1 bit per edge) consumes
n^2 * (1) bits of memory.
For a complete graph, an adjacency list (with 64 bit pointers) consumes
n * (n * 64) bits of memory, excluding list overhead.
For an incomplete graph, an adjacency list consumes
0 bits of memory, excluding list overhead.
For an adjacency list, you can use the follow formula to determine the maximum number of edges (
e) before an adjacency matrix is optimal for memory.
edges = n^2 / s to determine the maximum number of edges, where
s is the pointer size of the platform.
If you're graph is dynamically updating, you can maintain this efficiency with an average edge count (per node) of
n / s.
Some examples (with 64 bit pointers).
For a directed graph, where
n is 300, the optimal number of edges per node using an adjacency list is:
= 300 / 64 = 4
If we plug this into keyser5053's formula,
d = e / n^2 (where
e is the total edge count), we can see we are below the break point (
1 / s):
d = (4 * 300) / (300 * 300) d < 1/64 aka 0.0133 < 0.0156
However, 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 separat