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

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. It can be extended for parallel arcs and weighted graphs.

Space requirements:

Operations supported:

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.