Chapter 2

Graph Representation

Section 2.1 Computer Representations of Graphs

Alfred V. Aho

Columbia University

Introduction

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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.