Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
This seems to be my first ever question :)
Given that adjacency lists store all the necessary information with regards to the endpoints of an edge, we could even store a weight alongside that.
I don't understand why we would ever want to use an Edge List in a way that would be more useful than the above mentioned Adjacency List.
I had read on another that it may have to do with the sorting of Edges by weight. Is that something we can't accomplish with some other representation?
Thanks.
Any primitive operation that can be done with edge list, also can be done in adjacency list, but the main difference between them is time complexity of the primitive operations, for example, when you want find all adjacent vertices to some vertex $v$ the time complexity is $\Theta(|E|)$ but the same operation on adjacency list is $\Theta(deg(v))$ where $deg(v)$ is number of vertices that adjacent to vertex $v$ that in the worst case, if we have $n$ vertices it's equal to $\mathcal{O}(n)$, but doing that operation in edge list data structure in the worst case can be $\Theta(n^2)$ time.
On the other hand the space complexity of edge list is $\Theta(|E|)$, and adjacency list need the space $\Theta (|E|+|V|)$ and hence an edge list is more efficient in space complexity in some cases.
Is that something we can't accomplish with some other representation?
Edge list and adjacency list represent the same thing so if you can do something with one, you can do it with the other. In the worst case, you will have to convert one to the other.
When it comes to space, storing edge lists takes up less space than adjacency lists in most cases. For example, the adjacency list will take up less space for an undirected graph with high degree vertices.
A word about space complexity. We say that the space complexity is O(V+E) for the adjacency list and O(E) for the edge list. However, this is misleading. The edge list isn't asymptotically more space-efficient. The adjacency list's space complexity is O(V+E) because it can contain vertices with no edges which is something the edge list cannot do. To make the comparison fair, we should only consider graphs with no 0-degree vertices which can have at most 2E vertices, therefore, the space complexity of the adjacency list becomes O(E) as well.
In my experience, adjacency list is much faster than edge list in most cases. Of course, there will always be exceptions.
The operations where edge list is superior to the adjacency list are typically the ones that directly involve computing something about the edge list itself or straight up returning one. Here is a non-complete list of operations where the edge list is better:
For some operations, edge list will be faster but not asymptotically faster.
In some cases, operations with the edge list are so slow that it is worth converting it into an adjacency list just for that operation. For example, bfs search is O(V+E) time with adjacency list but O(V*E) for edge list because finding the neighbors of a vertex takes considerable time. This case is a tradeoff with space. The space complexity will increase from O(V) to O(E) (or O(V+E) which is the same thing as I discussed earlier.) which is very little next to the time gains.
Krystal’s algorithm for constructing minimum spanning trees first sorts an array of edges in increasing order of weight, so that edges with the smallest weight can be considered first for selection.
