Section 2.1 Computer Representations of Graphs
Alfred V. Aho
Many problems in science and engineering can be modeled in terms of directed and undirected graphs. The data structures and algorithms used to represent graphs can have a significant impact on the size of problems that can be implemented on a computer and the speed with which they can be solved. This section presents the fundamental representations used in computer programs for graphs and illustrates the tradeoffs among the representations using key algorithms for some of the most common graph problems.
Throughout this section we use the notation |X| to denote the number of elements in a set X. The graphs and digraphs ...