2. Adjacency List

Introduction

The Adjacency List is a 2D array used to represent the connections between vertices in a graph. It consists of an array of vertices, where each vertex maintains an array (or list) of its adjacent vertices.

• In an undirected graph, the Adjacency List represents each vertex's neighbors without considering the direction of edges.
• In a directed graph, the Adjacency List only saves the neighbors of each vertex that are connected by an outgoing edge (also known as successor).

Advantages

1. Efficient memory usage: In sparse graphs, where the number of edges is relatively small compared to the number of vertices, the adjacency list can be more memory-efficient compared to an adjacency matrix. It only requires storage proportional to the number of edges, rather than the square of the number of vertices.
2. Fast iteration over neighbors: With the adjacency list, it is easy to iterate over the neighbors of a vertex. Each vertex maintains a list or array of its adjacent vertices, allowing for efficient traversal and exploration of the graph.

Exercise