What is better, adjacency lists or adjacency matrices for graph problems in C++?

magiix picture magiix · Feb 7, 2010 · Viewed 138.8k times · Source

What is better, adjacency lists or adjacency matrix, for graph problems in C++? What are the advantages and disadvantages of each?

Answer

Mark Byers picture Mark Byers · Feb 7, 2010

It depends on the problem.

Adjacency Matrix

  • 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)

Adjacency List

  • 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
  • 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)