0
$\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 at 14:12
  • $\begingroup$ @nirshahar -> thank you for the clear reference to relevant use cases! $\endgroup$ Jul 18 at 16:00
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$
1
  • $\begingroup$ Thank you for the clear explanation. $\endgroup$ Jul 17 at 12:58

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.