CODEWITHSUNDEEP
graphadjacency-listdirected-graphadjacency-matrix
Adam Tango
Adam Tango

Reputation: 35

Directed Adjacency Lists

I have asked this question in a variety of ways, starting with:

When you have an adjacency list, does order matter? Say I had the adjacency list {1, 2, 5} is that equivalent to {2, 1, 5}? Or does order signify something and therefore these two lists are not equivalent?

I received several answers including it only matters if the graph is directed and the order signifies something to do with the adjacent nodes arrangement clockwise..? I also was given the opinion that no it does not matter, however he'd prefer it be ordered regarding weights (if used) such as the way the internet is ordered - page ranking algorithm. I don't presume to paraphrase any of these responses accurately although I think I conveyed the gist. Any thoughts are appreciated.

Also, I have refined my question in a way that if answered, I think will give me the exact answer I am after:

Suppose I have the adjacency matrix for a directed graph:

0 0 1 0

0 0 1 1

1 1 0 1

0 1 1 0

I am told the equivalent adjacency lists are as follows and presume my teacher listed it this way intentionally rather than some arbitrary reordering - especially as seen in the last list:

{ 2 }

{ 2, 3 }

{ 0, 1, 3 }

{ 2, 1 }

The last list is { 2, 1 }! What in the equivalent adjacency matrix alerts me that it should be { 2, 1 } rather than { 1, 2 }?

Upvotes: 1

Views: 2327

Answers (2)

pakpe
pakpe

Reputation: 5479

The value of a node in an adjacency list is a set. Sets are unordered. Therefore {1,2} is the same as {2,1}.

Upvotes: 0

voidengine
voidengine

Reputation: 2579

Typically, no, the order in adjacency list doesn't matter.

... unless explicitly stated.

Implementation may have the list actually ordered for various reasons: as a consequence of how the graph is created, or because you want to process neighbors of a vertex in some order. But conceptually, the order doesn't matter.

I believe that no is the answer in your case, {2,1} is the same as {1,2}. Perhaps your teacher wrote it wrong at first (like {2,3}) and didn't change the order after fixing it. Or he/she wanted you to go thinking whether the order does matter. Won't know for sure, unless you ask the teacher.

Upvotes: 2

Related Questions