What data structure should be used for graphs and graph algorithms? I am confused between Edgelist, adjacency list and adjacency matrix. Which one is the best and mostly used?
Adjacency list is used for sparse graphs .
Adjacency matrix is used for dense graphs .
A simple graph with n vertex can have n choose 2 edges . Hence the maximum numbers of edges can be O(n^2) . A graph is considered sparse if the total number of edges is O(n) and dense if it has O(n^2) edges .
It is not wise to store the edges simply as edge list as you should be able to know which vertices a given vertex is adjacent to in quick time . Also other problem scenarios and the kind of computation that needs to be done may play a role in deciding what representation you choose to have . However , the above mentioned categorization of sparse/dense graphs is always a guiding force .
It all depends on the task at hand and the situation you’re in.
Edgelist is easy to code, easy to debug, and space efficient. Determining the edges incident to a given vertex is, however, expensive. Determining if two vertices are adjacent is also expensive. But on the bright side, adding and edge is quick. But deleting one is difficult if the location on the list is not known. Though, Edgelist can handle undirected graphs, digraphs, and multigraphs simply.
Adjacency matrices are easy to code, but are not space efficient at all. It’s hard to debug, and finding all the edges incident to a given vertex is fairly expensive. But, checking if two vertices are adjacent is very quick, and adding or removing an edge is quick as well.
Adjancency lists are difficult to code and debug. But, it doesn’t use that much memory, and finding vertices adjacent to a node is easy. But, checking if two vertices are adjacent is difficult, and so is deleting an edge. Adding an edge is easy.
So here’s a list of needs and the best data structures that accomplish those needs.
Space: Edge list or Adjacency List
Adjacency Check: Adjacency Matrix
List of adjacent vertices: depends on how large the graph is.
Adding an edge: They’re all good
Deleting an edge: Adjacency matrix.
Those are your options IF implicit representation is not an option. If you can implicitly represent the graph (that is, without a data structure), do it. It saves space, time, etc.