Compare Adjacency Lists or Adjacency Matrices for Graphs representation

In graph theory, a graph representation is a technique to store graph into the memory of computer.

• Adjacency Matrix. Adjacency matrix is a sequential representation so it can be represented as an array. In this representation, we have to construct a NxN matrix A. If there is any edge from a vertex i to vertex j, then the corresponding element of A, a(i, j) = 1, otherwise a(i, j)= 0.
• Pros:
  • Representation is easier to implement and follow
  • It is fast to lookup and check for presence or absence of a specific edge between any two nodes O(1)
  • It is fast to add a new edge O(1)
• Cons:
  • It takes a lot of space (O(n2) space complexity)
  • Inefficient when the graph is sparse, meaning that there is a lot less edges than N2 nodes.
  • It is slow to iterate over all edges
  • It is slow to add/delete a node; a complex operation O(n2)

• Adjacency List. Adjacency list is a linked representation. In this representation, for each vertex in the graph, we maintain the list of its neighbours. It means, every vertex of the graph contains list of its adjacent vertices.
• Pros:
  • Memory usage depends on the number of edges (not number of nodes), which might save a lot of memory if the adjacency matrix is sparse
  • 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)
• Cons:
  • 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 neighbours nodes