2.1 Representing Graphs as Lists
The most obvious data structure for representing a graph arises directly from its definition. is described by two simple lists:
A vertex list , and
An edge list which represents each edge as a pair of vertices.
This data structure often forms the basis of the interface between the user and graph algorithms. The reasons are twofold:
For many people, it is the most “natural” way to describe the connections in a graph.
It is a relatively efficient way to represent sparse graphs.
As an example, consider the directed graph of Figure 1. It has six vertices. Its vertex list is simply
The directed graph in Figure 1 has ten edges. Its edge list follows.
The corresponding undirected graph shown in Figure 2 has the same six vertices.
However, it has 16 edges.