---

Graph Representation

---

Graphs are fundamental data structures used to represent relationships between entities. To store and manipulate these relationships efficiently, several different graph representations exist. Here's an overview of the most common ones:

1. Adjacency Matrix
2. Adjacency List

Adjacency Matrix

An adjacency matrix is a 2D array where each cell [i, j] represents the presence or absence of an edge between vertices i and j. If the graph is weighted, the cell can store the weight of the edge.

Here's an overview of the key aspects of adjacency matrices:

Adjacency Matrix Structure

Let G =(V,E) be a graph with n nodes, n>0. a_ij is an adjacency matrix of G. The a_ij is an n x n array whose elements are given by

$$a_{\mathrm{ij}}=\{\begin{array}{ll}1& if(v_{\mathrm{i}},v_{\mathrm{j}})\in E\\ 0& otherwise\end{array}$$

• The adjacency matrix is a square matrix of size N x N, where N is the number of vertices in the graph.
• Each element (i, j) of the matrix represents the presence (1) or absence (0) of an edge between vertex i and vertex j.
• For undirected graphs, the matrix is symmetric, meaning a[i][j] = a[j][i].
• For directed graphs, the adjacency matrix is not necessarily symmetric, meaning a[i][j] ≠ a[j][i].

Advantages of Adjacency Matrix

• Efficient for dense graphs.
• Quick to check if there is an edge between two vertices.

Disadvantages of Adjacency Matrix

• Requires more space, as it allocates memory for every possible edge, which is impractical for large sparse graphs.
• Adding or removing vertices involves resizing the matrix, which can be inefficient.

Adjacency List

The n rows of adjacency matrix are represented as n linked lists. There is one list for each vertex in the graph. The nodes in the list i represent the vertices that are adjacent from vertex i. Each node has at least two fields: vertex and link. The vertex field contains the indices of the vertices adjacent to vertex i. The adjacency lists for the undirected graph and directed graph, are illustrated below.

Here's an overview of the key features of adjacency lists:

Adjacency List Structure

• Each vertex in the graph has a corresponding list.
• This list stores the identifiers of all the vertices connected to the original vertex by an edge.
• The list can be implemented using different data structures like arrays, linked lists, or even hash tables.
• The implementation choice depends on the desired functionality and performance characteristics.

Advantages of Adjacency List

• Space-efficient for sparse graphs (graphs with relatively few edges compared to the number of vertices).
• Easy to add vertices and edges.
• Efficient in finding all adjacent vertices of a given vertex.

Disadvantages of Adjacency List

• Can be less efficient for dense graphs (where the number of edges is close to the maximum possible).
• Determining whether an edge exists between two vertices can be less efficient than with an adjacency matrix.

---

Next Topic :Breadth-First Search