1. Adjacency Matrix

Introduction

The Adjacency Matrix is a n by n matrix used to represent the connections between n vertices in a graph. In the adjacency matrix, rows and columns correspond to vertices, with each cell A[i][j] being filled with 1 if vertices i and j are connected, and 0 otherwise. It can also be a weighted value if the graph includes edge weights.

• In an undirected graph, the adjacency matrix is symmetric, meaning A[i][j] equals A[j][i].
• In a directed graph, the adjacency matrix is not necessarily symmetric. A[i][j] represents the existence of an edge directed from vertex i to vertex j

It is often used to efficiently analyze graphs, determine connectivity, and perform various graph algorithms.

Advantages

1. Efficient edge lookup: With the adjacency matrix, it is easy to determine if there is an edge between any two vertices, as the connectivity information is directly stored in the matrix.
2. Space efficiency: In dense graphs, where most vertices are connected to many others, the adjacency matrix can be more space-efficient compared to an adjacency list. It only requires a square matrix of size n by n, where n is the number of vertices, regardless of the number of edges.

Exercise