Input Description: A graph \(G\).
Problem: Give an efficient, flexible data structure to represent \(G\).
Excerpt from The Algorithm Design Manual: While there are several possible variations, the two basic data structures for graphs are adjacency matrices and adjacency lists.
Building a good general-purpose graph type is surprisingly tricky and difficult. For this reason, we suggest that you check out existing implementations (particularly LEDA) before hacking up your own. Note that it costs only time linear in the size of the larger data structure to convert between adjacency matrices and adjacency lists. This conversion is unlikely to be the bottleneck in any application, if you decide you want to use both data structures and have the space to store them. This usually isn't necessary but might prove simplest if you are confused about the alternatives.
|Guava (rating 10)
||C++ Boost Graph Library (rating 10)
|LEDA (rating 10)
||Boost Graph Library (rating 9)
|JUNG (rating 9)
||gonum (rating 8)
|JGraphT (rating 8)
||JDSL (rating 8)
|networkx (rating 7)
||Stanford Graphbase (rating 0)
|Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica by S. Pemmaraju and S. Skiena||Combinatorial Algorithms for Integrated Circuit Layout by T. Lengauer||Handbook of Theoretical Computer Science : Algorithms and Complexity by J. Van Leeuwen|
|Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein||Data Structures and Network Algorithms by R. Tarjan||Data Structures and Algorithms by A. Aho and J. Hopcroft and J. Ullman|