I know there are two ways to represent my graph: one is using a matrix, and the other one is using a list. If I use a matrix, I have to flip all the bits in the matrix. Doesn't that take O(V^2) time? If I use a list, wouldn't I have to traverse each list, one by one, and create a new set? That would seem to take O(V+E) time which is linear. Am I correct? So, I got another question here. Consider, for example, that I use the Dijkstra algorithm on my graph (either a matrix or a list), and we use a priority queue for the data structure behind the scene. Is there any relation of graph representation and the use of data structure? Will it affect the performance of the algorithm? Suppose I were to use a list for representations and a priority queue for the Dijkstra algorithm, would there be a difference between matrix and use priority queue for Dijkstra? I guess it relates to makeQueue operation only? Or they don't have different at all?
59.2k 19 19 gold badges 148 148 silver badges 150 150 bronze badges asked Apr 23, 2013 at 0:23 Timothy Leung Timothy Leung 1,465 7 7 gold badges 23 23 silver badges 41 41 bronze badges Traversal of adjacency lists does Not Happen in linear Time in General as E=O(V^2). Commented Apr 23, 2013 at 7:26@collapsar It always happens in linear time with relation to the vertices and edges. To define time complexity only on a part of the input (i.e. just vertices) (without explicitly stating it) seems somewhat illogical, especially when the time is directly related to another part of the input (but I can't argue that many people may define it as you did). And E = O(V^2) is for dense graphs. Sparse graphs are E = O(V).
Commented Apr 23, 2013 at 7:53@dukeling you are right in pointing out that reducing the 'size' of a problem to a single scalar involves a lack of precision. otoh, big-Oh notation describes the worst case and, considering graphs, without additional constraints worst case means E=O(V^2). being precise, O(V^2) is not correct for edge reversal on an adjacency matrix either - if the representation sports a flag row-major vs. col-major, transposition is O(1).
Commented Apr 23, 2013 at 8:50> If I use a matrix, I have to flip all the bits in the matrix. \\ Wouldn't you want to transpose it instead?