1
$\begingroup$

So generally speaking, when we implement the graph using linked list, do we store the degree of each edge too?

I'm asking this because if a question in my exam stated that we implemented this graph using linked list, do i assume we can access the degree of each edge in o(1) or not? this matters because it effects the time complexity of algorithms like finding if the graph has euler cycle which i should check the degree of each edge

and the exams are SAT type of questions so i can't write down anything i should just choose one of the 4 answers which for example says the time complexity of finding if the graph has euler path in linked list implementation

$\endgroup$
  • $\begingroup$ It's up to you. Usually the degree isn't stored explicitly, but you can deduce the out-degree by comparing the "next" pointer to NULL. As for the convention used in your course, it's up to your professor, so you'll have to ask them. $\endgroup$ – Yuval Filmus Apr 3 '18 at 11:06
  • $\begingroup$ @YuvalFilmus but is there any advantage in not storing the degree? for example why don't all the implementations store the degree in linked list and only some of them do? why not just store the degree as well? i mean the overhead is almost non existence because even if you delete an edge you only need to reduce the number of degree so its not a lot of overhead. $\endgroup$ – John P Apr 3 '18 at 11:41
  • $\begingroup$ You just explained the advantage - the degree takes up space, and you also have to maintain it. In order to maintain it, you actually need a doubly linked list, which takes up even more space. You could store a lot of things at every node, such as a pointer to the first and the last node of the list. This might be helpful in some cases, but if it isn't, there is no need to. $\endgroup$ – Yuval Filmus Apr 3 '18 at 11:44
  • $\begingroup$ @YuvalFilmus but what about storing it in the head node? like instead of having a 2 attribute head node we add one more attribute for degree, and the only overhead would be O(1) to increase or decrees it which is when we delete or add a new edge, i mean we already had the head node so basically there is no wasted space right? but not even one website implemented the linked list like this which i don't get why! $\endgroup$ – John P Apr 3 '18 at 11:53
  • $\begingroup$ Every information that you store potentially uses up space (sometimes it doesn't due to padding issues). At this point, I suggest contacting a TA or your professor for any further information. $\endgroup$ – Yuval Filmus Apr 3 '18 at 11:54
2
$\begingroup$

Normally we don't; the adjacency list representation is a list of out-edges, but doesn't separately store the degree. However, you can certainly store that additional information if you want. You can choose how you want to represent the graph, and it's not hard to modify the standard data structure to keep track of the out-degree of each vertex.

$\endgroup$
  • $\begingroup$ So one question, the only downside of having to store the degree in the head node is the wasted space right? (since operations like decreasing it when an edge is removed is done in o(1) ). but considering we are just adding an additional attribute to the head nodes, is the wasted space noticeable? is it O(n)? because i really don't understand why most of the linked lists don't store degree! every website i saw did not store degree, why don't they want to check the degree in O(1) instead of O(e) ? $\endgroup$ – John P Apr 3 '18 at 16:43
  • $\begingroup$ @JohnP, right. Yup, $O(n)$. Doesn't affect the asymptotic space usage; might or might not be noticeable in practice. $\endgroup$ – D.W. Apr 3 '18 at 17:36

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.