What is better, adjacency lists or adjacency matrix, for graph problems in C++? What are the advantages and disadvantages of each?
11 Answers
It depends on the problem.
- Uses O(n^2) memory
- It is fast to lookup and check for presence or absence of a specific edge
between any two nodes O(1) - It is slow to iterate over all edges
- It is slow to add/delete a node; a complex operation O(n^2)
- It is fast to add a new edge O(1)
- Memory usage depends more on the number of edges (and less on the number of nodes),
which might save a lot of memory if the adjacency matrix is sparse - Finding the presence or absence of specific edge between any two nodes
is slightly slower than with the matrix O(k); where k is the number of neighbors nodes - It is fast to iterate over all edges because you can access any node neighbors directly
- It is fast to add/delete a node; easier than the matrix representation
- It fast to add a new edge O(1)
It depends on what you're looking for.
With adjacency matrices you can answer fast to questions regarding if a specific edge between 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.
EDIT
This previous question on SO will probably help:
how-to-create-a-c-boost-undirected-graph-and-traverse-it-in-depth-first-search
I am just going to touch on overcoming the trade-off of regular adjacency list representation, since other answers have covered those 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 would be O(V) amortized like in adjacency matrix with an array index lookup dictionary. 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.
Related