What type of application is each data structure for storing edges of a graph best suited for?

0
votes

This is from a practice test I'm working on...not sure how to answer this one:

Consider the three data structures for storing edges (adjacency matrix, adjacency list, edge list) in a graph. What type of application is each data structure best suited for?

Correct me if I'm wrong but to my knowledge an adjacency matrix is the least efficient way to represent a graph because there are elements in the two-dimensional array that represent non-existant edges where as the other two data structures only contain elements that represent existant edges so traversal for any operation is slower. If this is true then why would anyone want to use it?

And as for an adjacency list, it is more efficient than an adjacency matrix, but still contains redundant information --> If an edge joins vertices i and j then a vertex node containing vertex i appears in the adjacency list for vertex j and at the same time the vertex node containing vertex j appears in the adjacency list for vertex i.

And...the edge list is the most efficient.

So reiterating my question.... If an edge list is the most efficient representation, why would you ever want to use one of the other two instead?

Any help would be appreciated, thanks.

1
c++data-structuresgraph
Adjacency list can be very eficient considering memory, so it has it's uses too. - Jaa-c
Adjacency matrices are very efficient for small or dense graphs, as you can pack edges as bits. - Elliot Robinson
Google has the answer - nishantjr
@Jaa-c Ah I can see why! Since there can be many more edges than nodes most of the time. - Riptyde4
Conversely, very sparse graphs still require you to store all those 0'ed bits, but have very few 1s. There is some tradeoff point where it is less expensive to store a list of edges than to store a matrix, even doing bit packing. - Elliot Robinson

1 Answers

0
votes

You're talking only about space efficiency. There's also time. If you have the vertex numbers, a matrix requires only one or a couple of instructions to find the edge value. You can't get faster. It's also very simple to implement and maintain. (A down side is that it takes O(n^2) to initialize regardless of edge count. But there's a fix for that.) The other forms all involve some kind of searching. Even if you do the adjacency lists as hashes for O(1) access, the constant factor of time is much higher than for the matrix. The edge list only makes sense if you are processing edges and never need to look up an edge based on its vertices.