Page 72 - Data Structures Interactive Book

8.2 Representation of Graphs

Graphs can be represented in different ways depending on the application. The two

most common representations are adjacency matrices and adjacency lists.

8.2.1 Adjacency Matrix

An adjacency matrix is a two-dimensional array of size × , where is the number

of vertices in the graph. Each cell [ ][ ]indicates whether there is an edge between vertex

and vertex . For unweighted graphs, the value is typically 1 if an edge exists and 0 otherwise.
For weighted graphs, the cell stores the weight of the edge, and 0 or ∞ (infinity) indicates no

edge.

This representation is straightforward and allows constant-time edge lookup, which is

useful when checking whether two vertices are directly connected. However, it consumes

( )⁡memory, which can be inefficient for sparse graphs with few edges compared to the
number of vertices.

Example: Adjacency Matrix in C++

This program creates a simple directed graph with four vertices and prints its adjacency matrix.
The matrix clearly shows which vertices are connected.
72