2.2 Representing Graphs as Adjaceny Matrices

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

aij=1when vertex i is adjacent to vertex j0when 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 V2|V|^{2}. When GG is represented as an adjacency matrix, the best time complexity you can expect for graph algorithms is OV2O\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.

Adigraph=001000101100010010000001000100000110A_{{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.

Aundirected=011000101100110010010011001101000110A_{{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.