2.2 Representing Graphs as Adjaceny Matrices

An alternate representation of G G is known as an adjacency matrix. In this data structure, a V × V |V|\times|V| matrix A \mathbf{A} is established such that

a i j = 1 when vertex  i  is adjacent to vertex  j 0 when vertex  i  is not adjacent to vertex  j {a}_{{ij}}=\begin{cases}1&\mbox{when vertex }i\mbox{ is adjacent to vertex }j\\ 0&\mbox{when vertex }i\mbox{ is not adjacent to vertex }j\end{cases} (1)

The storage required to implement an adjacency matrix is proportional to V 2 |V|^{2} . When G G is represented as an adjacency matrix, the best time complexity you can expect for graph algorithms is O V 2 O\left(|V|^{2}\right) . This is the time required to access each element of the matrix exactly one time.

Once again consider the directed graph of Figure 1. Its adjacency matrix follows.

A d i g r a p h = 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 A_{{digraph}}=\left(\begin{array}[]{cccccc}0&0&1&0&0&0\\ 1&0&1&1&0&0\\ 0&1&0&0&1&0\\ 0&0&0&0&0&1\\ 0&0&0&1&0&0\\ 0&0&0&1&1&0\\ \end{array}\right)

The adjacency matrix of the undirected version of the graph (Figure 2) is as follows.

A u n d i r e c t e d = 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 A_{{undirected}}=\left(\begin{array}[]{cccccc}0&1&1&0&0&0\\ 1&0&1&1&0&0\\ 1&1&0&0&1&0\\ 0&1&0&0&1&1\\ 0&0&1&1&0&1\\ 0&0&0&1&1&0\\ \end{array}\right)

Observe that the adjacency matrix of an undirected graph is symmetric.