Just started learning about graph and it's various representations (matrix and adjacency list). Now I found that the adjacency list representation can be implemented in various ways:

  1. Array of arrays (where we have one index in main array for each vertices and adjacent vertices are in subarrays at each of this index)
  2. Array of linked lists (most common implementation I have seen)
  3. Map of array (same as array of arrays, except that outer array is now a Map)

Was wondering why would I prefer one of these implementation over the other. Is one implementation more common or efficient in any way or they all the same?

  • $\begingroup$ Every structure has advantages and is more efficient in some usages. You even can imagine other structures for very specific usages. For these ones, I am pretty sure you can find alone the main pros and cons of each one... Are these structures efficient for static or dynamic graphs ? For sparse or dense graphs ? $\endgroup$
    – Optidad
    Sep 24 '20 at 21:39
  • $\begingroup$ (Farzan and Munro seem to start with the matrix.) $\endgroup$
    – greybeard
    Sep 26 '20 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.