Question concerning adjacency lists

[Mehes Andrew F J]

Hello, I was just wondering, in cases where we are asked to find the
complexity of finding, for example, if 2 given edges are adjacent in an
adjacnecy list, do we assume that we already know where one of the two
vertices is stored in the adjacency list array or do we have to have
account for traversing the matix. in other words, would the worse case for
this scenario be O(V+E) or O(V)?

Thank you.

[Alexander Smith]

If the question says you are given both edges, then you don't need to
search for them. Look at the diagram on page 12 of the "Graphs Part I"
lecture notes. In this case, you just need to traverse the linked-list of
edges for one of the two given vertices. O(V) is a correct bound, but
unless you know that your graph is dense (rather than sparse), it's
probably not the best way to express it. If you look at the table on page
14 of the notes, you'll see that it says the answer is "O(d)", where d is
the degree of the vertex.

Alexander

[Mehes Andrew F J]

Thank you.