# 2.1 Representing Graphs as Lists

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

• A vertex list $V(G)$, and

• An edge list $E(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

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

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

 $E(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.

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

However, it has 16 edges.

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