Talk:Adjacency list

From Wikipedia, the free encyclopedia

The link to "Incidence Lists" takes you to the same page as "Adjacency Lists". http://en.wikipedia.org/wiki/Incidence_list

The article makes the clame: " Besides the space tradeoff, the different data structures also facilitate different operations. It's easy to find all vertices adjacent to a given vertex in an adjacency list representation; you simply read its adjacency list. With an adjacency matrix you must instead scan over an entire row, taking O(n) time. If you, instead, want to know if two given vertices have an edge between them, this can be determined at once with an adjacency matrix, while requiring time proportional to the minimum degree of the vertices with the adjacency list. "

But this is not shown to be true by Designing Fast Graph Data Structures: An Experimental Approach http://citeseer.ist.psu.edu/358648.html In this paper it is shown that a bit packed adjacency matrix is the most proforment data structure. This section should be updated to reflect this. —Preceding unsigned comment added by Wikiwikimoore (talk • contribs) 21:48, 19 December 2007 (UTC)