1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Welcome to the site! An edge list gives a natural way to pre-emptively sort all edges by weight, meaning that using algorithms that require this ordering can be done faster (such as Kruskal's algorithm), assuming we are already given this sorting. On the other hand, in other representations, you will have to convert them to an edge list and manually sort it, before using it in those algorithms, meaning that it will increase the run-time of such algorithms (this is exactly why Kruskal takes $\Theta(|E|\log(|E|))$ and not less). $\endgroup$
    – nir shahar
    Jul 17, 2021 at 14:12
  • $\begingroup$ @nirshahar -> thank you for the clear reference to relevant use cases! $\endgroup$ Jul 18, 2021 at 16:00

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for the clear explanation. $\endgroup$ Jul 17, 2021 at 12:58
  • $\begingroup$ Asymptotically, the edge list isn't more space-efficient. The adjacency list's space complexity is O(E+V) because it can contain vertexes 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 vertexes which can have at most 2E vertexes, therefore, the space complexity of the adjacency list becomes O(E) as well. $\endgroup$ May 14 at 2:30
0
$\begingroup$

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.

Storage

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.

Speed

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:

  • Getting the list of edges
  • Getting the number of edges
  • ...

For some operations, edge list will be faster but not asymptotically faster.

  • Getting the sum of edge weights
  • Getting sorted edge weights
  • ...

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.