A New Graph Data Structure
Brandon Sorg · The Knowledge Bank (The Ohio State University) · 2010
A new data structure for graph representation has at least as good time efficiency as either of the two traditional data structures, the adjacency matrix and adjacency list, for any graph algorithm. For some algorithms, this new data structure actually produces a lower asymptotic bound than either of the other two. It is overall faster in practice as well and perhaps the best choice for general-purpose graph representation. A general-purpose sub-data structure is used to implement this new graph data structure and has applications of its own outside graph implementation.