1.1.4 Graph Data Structures
INPUT OUTPUT
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.
- How big will your graph be? How many vertices will it have, both typically and in the worse case?
Ditto for the number of edges? If your graph has 100 vertices, your adjacency matrix contains 10,000 entries.
If your graph has 1,000 vertices, your adjacency matrix contains 1,000,000 entries. If your graph has 10,000
vertices, your adjacency matrix contains 100,000,000 entries -- so forget about it. Adjacency matrices work only
for small or very dense graphs.
- How dense will your graph be? If the graph is very dense, meaning that a large fraction of the
vertex pairs define edges, there is probably no compelling reason to use adjacency lists, since you will be
doomed to using Theta(n2) space, anyway.
- Which algorithms will you be implementing? Certain algorithms are easier on adjacency matrices
(such as all-pairs shortest path) and others on adjacency lists (such as most DFS-based algorithms).
Adjacency matrices win for algorithms that repeatedly ask, ``Is (i,j) in G?'' However, most graph algorithms can be
modified to eliminate such queries.
- Will you be modifying the graph over the course of your application, and if so, how? Repeated edge
insertions and (particularly) deletions argue for adjacency matrices, or perhaps for fancier versions of
adjacency lists such as binary search trees. However, more likely than modifying the topology of graph
is modifying the attributes of a vertex or edge of the graph, such as size, weight, or color. Attributes
are best handled as extra fields in the vertex or edge records of 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.
Recommended Books
Related Problems
This page last modified on 2008-07-10
.
www.algorist.com
Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica
Combinatorial Algorithms for Integrated Circuit Layout
Introduction to Algorithms
Data Structures and Network Algorithms
Data Structures and Algorithms
