2.1 Representing Graphs as Lists

The most obvious data structure for representing a graph arises directly from its definition. GG is described by two simple lists:

  • A vertex list VGV(G), and

  • An edge list EGE(G) 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

VGdigraph=1,2,3,4,5,6V(G)_{{digraph}}=\left\{ 1,2,3,4,5,6\right\}

The directed graph in Figure 1 has ten edges. Its edge list follows.

EGdigraph=1,3,2,12,3,2,4,3,2,3,5,4,6,5,4,6,4,6,5E(G)_{{digraph}}=\left\{(1,3),(2,1)(2,3),(2,4),(3,2),(3,5),(4,6),(5,4),(6,4),(6,5)\right\}

The corresponding undirected graph shown in Figure 2 has the same six vertices.

VGundirected=1,2,3,4,5,6V(G)_{{undirected}}=\left\{ 1,2,3,4,5,6\right\}

However, it has 16 edges.

E(G)undirected={\displaystyle E(G)_{{undirected}}=\{1,2,1,3,2,12,3,2,4,3,1,3,2,3,5,\displaystyle(1,2),(1,3),(2,1)(2,3),(2,4),(3,1),(3,2),(3,5),
(4,2),(4,5),(4,6),(5,3),(5,4),(5,6),(6,4),(6,5)}\displaystyle(4,2),(4,5),(4,6),(5,3),(5,4),(5,6),(6,4),(6,5)\}