Graph Representation in Memory

Internal

• Graphs

Overview

TODO CLRS page 589, DDIA location 1392.

Graph Input Size

When it comes to graphs, the input size is given by two parameters: the number of vertices (n) and the number of edges (m).

For a connected, undirected graph with n vertices, the number of edges ranges from n - 1 and n (n - 1)/2.

Adjacency Lists

A data structure that keeps track of vertices and edges as independent entities. It has an array (or a list) of vertices and an array (or a list) of edges. These two arrays cross-reference each other. Each edge points to its endpoints. Each vertex points to all of its edges it is a member. Applies to directed and undirected graphs.

An adjacency list representation provides a memory-efficient way of representing sparse graphs, so it is usually the method of choice.

Continue CLRS page 590.

Adjacency Matrices

The edges of a graph are represented using a matrix. Applies to directed and undirected graphs. The matrix is denoted by A, and it is a nxn square matrix, where n is the number of vertices in the graph. The semantics is A_ij=1 if and only if there's an edge between vertices i and j in the graph. It can be extended for parallel arcs and weighted graphs. For parallel arcs, A_ij denotes the number of edges. For weighted graphs, A_ij denotes the weight of the edge. For directed graphs, if the arc is directed from i to j, A_ij=+1 and if it is directed from j to i, A_ij=-1.

Space requirements: an adjacency matrix requires space quadratic in the number of vertices Θ(n²). For dense graphs this is fine but for sparse graphs, it is wasteful.

Cases when adjacency matrix representation is preferred:

• dense graphs.
• When we need to tell quickly if there is an edge connecting two given vertices.

CLRS page 590.