n two vertices belongs to the graph, and you can also have quick insertions and deletions of edges. The downside is that you have to use excessive space, especially for graphs with many vertices, which is very inefficient especially if your graph is sparse.
On the other hand, with adjacency lists it is harder to check whether a given edge is in a graph, because you have to search through the appropriate list to find the edge, but they are more space efficient.
Generally though, adjacency lists are the right data structure for most applications of graphs.
If you are looking at graph analysis in C++ probably the first place to start would be the boost graph library, which implements a number of algorithms including BFS.
This previous question on SO will probably help:
Lets assume we have a graph which has n number of nodes and m number of edges,
Adjacency Matrix: We are creating a matrix that has n number of rows and columns so in memory it will take space that is proportional to n2. Checking if two nodes named as u and v has an edge between them will take Θ(1) time. For example checking for (1, 2) is an edge will look like as follows in the code:
if(matrix == 1)
If you want to identify all edges, you have to iterate over matrix at this will require two nested loops and it will take Θ(n2). (You may just use the upper triangular part of the matrix to determine all edges but it will be again Θ(n2))
Adjacency List: We are creating a list that each node also points to another list. Your list will have n elements and each element will point to a list that has number of items that is equal to number of neighbors of this node (look image for better visualization). So it will take space in memory that is proportional to n+m. Checking if (u, v) is an edge will take O(deg(u)) time in which deg(u) equals number of neighbors of u. Because at most, you have to iterate over the list that is pointed by the u. Identifying all edges will take Θ(n+m).
Adjacency list of example graph
This is best answered with examples.
Think of Floyd-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
H