Graph Algorithms - Edge List to Adjacency list or Adjacency Matrix

Ecnoir 0
Viewed 17

When working with Graph Algorithms, it seems most of the solutions are given in terms of the adjacency list or the adjacency matrix representation of graphs.

However, I see most of the problems in leetcode are provided as an edge list. Since most of the solutions are given not using an edge list is it a good idea to convert the edge list to an adjacency list or the adjacency matrix? Is it recommended to solve all the problems using edge lists? Following are some of the basic Graph related problems:

  1. Cycle check in Graph
  2. Find path between two nodes in a Graph
  3. Find shortest path between two nodes in a Graph
graph data-structures algorithm
2 Answers

It all depends!

For large sparse graphs ( i.e. many nodes but few edges ) the adjacency matrix consumes a lot of memory which an adjacency list does not.

If you are dealing with small graphs ( < 1000 nodes ) or large graphs with even larger numbers of edges then it does not matter which you use.

The above assumes that you have an efficient data structure and good design.

ravenspoint0

If I understand correctly, an edge list is just a list of vertex pairs in no particular order, whereas an adjacency list is a well known data structure where each item in the list contains a source vertex and a nested list of the destination vertices for that source.

In that sense, an adjacency list is just a better structure: it takes less space and going through the out edges of a particular vertex is trivial (as opposed to a search, even if it's a binary search through a sorted list of edges).

So to answer the question, yes, it's a good idea to convert an edge list to an adjacency list, unless the problem is trivial to solve with a simple list of edges.

As for adjacency matrices: they have advantages, like locality of reference and the fact they can be packed smaller than adjacency lists in some situations.

Nelfeal0
Related