Chapter 22. Elementary Graph Algorithms¶
This chapter discusses:
- Representing a graph
- Searching a graph
22.1 Representations of graphs¶
There are two standard ways to represent a graph G = (V, E):
- (A collection of) adjacency lists
- An adjacency matrix
Choices:
- The adjacency-list representation provides a compact way to represent sparse graphs (where |E| is much less than |V|2); it is usually the method of choice. Most of the graph algorithms presented in this book assume that an input graph is represented in adjacency-list form.
- The adjacency-matrix representation is preferred when the graph is dense (|E| is close to |V|2).
The following figure shows two representations of an undirected graph. (a) An undirected graph G with 5 vertices and 7 edges. (b) An adjacency-list representation of G. (c) The adjacency-matrix representation of G.
The following figure shows two representations of a directed graph. (a) A directed graph G with 6 vertices and 8 edges. (b) An adjacency-list representation of G. (c) The adjacency-matrix representation of G.
The adjacency-list representation of a graph G = (V, E) consists of an array Adj of |V| lists, one for each vertex in V . For each u ∈ V , the adjacency list Adj[u]" contains all the vertices v such that there is an edge (u, v) ∈ E. That is, Adj[u]" consists of all the vertices adjacent to u in G.
- If G is a directed graph, the sum of the lengths of all the adjacency lists is |E|, since an edge of the form (u, v) is represented by having v appear in Adj[u].
- If G is an undirected graph, the sum of the lengths of all the adjacency lists is 2|E|, , since if (u, v) is an undirected edge, then u appears in v's adjacency list and vice versa.
[p591]
A potential disadvantage of the adjacency-list representation is that it provides no quicker way to determine whether a given edge (u, v) is present in the graph than to search for v in the adjacency list Adj[u]. An adjacency-matrix representation of the graph remedies this disadvantage, but at the cost of using asymptotically more memory.
We can readily adapt adjacency lists to represent weighted graphs (graphs for which each edge has an associated weight), typically given by a weight function w. We simply store the weight w(u, v) of the edge (u, v) with vertex v in u’s adjacency list.
[p591-592]
Representing attributes¶
[p592]
For example, in an object-oriented programming language, vertex attributes might be represented as instance variables within a subclass of a Vertex class