2.2 Representing Graphs as Adjaceny Matrices ‣ 2 Modeling Graphs ‣ Graph Algorithms

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

{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}$ . When $G$ is represented as an adjacency matrix, the best time complexity you can expect for graph algorithms is $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_{{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_{{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.