Chapter 2

Graph Representation

Section 2.1 Computer Representations of Graphs

Alfred V. Aho

Columbia University


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 ...

Get Handbook of Graph Theory, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.