2.1 Representing Graphs as Lists ‣ 2 Modeling Graphs ‣ Graph Algorithms

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

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)\}$