Adjacency Matrix

We have already defined graphs in set-theoretic termsAs a set of vertices and a set of edges and represented them pictorially to impart intuition. However, we need an alternate representation that facilitates working with graphs algorithmically.

One such representation is the adjacency matrix representation. Using this representation, graphs can be stored as two-dimensional arrays.

Adjacency matrix for a simple graph

An adjacency matrix $A$ for a simple graphRecall that a graph is simple if it has at most one edge between a pair of vertices and if it has no loops. on $n$ vertices is an $n\times n$ matrix having the following properties:

1. The $i^{th}$ row and $i^{th}$ column are associated with the same vertex, say $v_i$.
2. The value $a_{i,j}$

...