12.1 $ \mathtt{AdjacencyMatrix}$: Representing a Graph by a Matrix

An adjacency matrix is a way of representing an $ \mathtt{n}$ vertex graph $ G=(V,E)$ by an $ \ensuremath{\mathtt{n}}\times\ensuremath{\mathtt{n}}$ matrix, $ \mathtt{a}$, whose entries are boolean values.

  int n;
  bool **a;

The matrix entry $ \mathtt{a[i][j]}$ is defined as

$\displaystyle \ensuremath{\mathtt{a[i][j]}}=
\begin{cases}
\ensuremath{\math...
...(i,j)}}\in E$} \\
\ensuremath{\mathtt{false}} & \text{otherwise}
\end{cases}$

The adjacency matrix for the graph in Figure 12.1 is shown in Figure 12.2.

With this representation, the $ \mathtt{addEdge(i,j)}$, $ \mathtt{removeEdge(i,j)}$, and $ \mathtt{hasEdge(i,j)}$ operations just involve setting or reading the matrix entry $ \mathtt{a[i][j]}$:

  void addEdge(int i, int j) {
    a[i][j] = true;
  }
  void removeEdge(int i, int j) {
    a[i][j] = false;
  }
  bool hasEdge(int i, int j) {
    return a[i][j];
  }
These operations clearly take constant time per operation.

Figure 12.2: A graph and its adjacency matrix.
\includegraphics{figs/graph}



  0 1 2 3 4 5 6 7 8 9 10 11
0 0 1 0 0 1 0 0 0 0 0 0 0
1 1 0 1 0 0 1 1 0 0 0 0 0
2 1 0 0 1 0 0 1 0 0 0 0 0
3 0 0 1 0 0 0 0 1 0 0 0 0
4 1 0 0 0 0 1 0 0 1 0 0 0
5 0 1 1 0 1 0 1 0 0 1 0 0
6 0 0 1 0 0 1 0 1 0 0 1 0
7 0 0 0 1 0 0 1 0 0 0 0 1
8 0 0 0 0 1 0 0 0 0 1 0 0
9 0 0 0 0 0 1 0 0 1 0 1 0
10 0 0 0 0 0 0 1 0 0 1 0 1
11 0 0 0 0 0 0 0 1 0 0 1 0

Where the adjacency matrix performs poorly is with the $ \mathtt{outEdges(i)}$ and $ \mathtt{inEdges(i)}$ operations. To implement these, we must scan all $ \mathtt{n}$ entries in the corresponding row or column of $ \mathtt{a}$ and gather up all the indices, $ \mathtt{j}$, where $ \mathtt{a[i][j]}$, respectively $ \mathtt{a[j][i]}$, is true.

  void outEdges(int i, List &edges) {
    for (int j = 0; j < n; j++)
      if (a[i][j]) edges.add(j);
  }
  void inEdges(int i, List &edges) {
    for (int j = 0; j < n; j++)
      if (a[j][i]) edges.add(j);
  }
These operations clearly take $ O(\ensuremath{\mathtt{n}})$ time per operation.

Another drawback of the adjacency matrix representation is that it is big. It stores an $ \ensuremath{\mathtt{n}}\times\ensuremath{\mathtt{n}}$ boolean matrix, so it requires at least $ \ensuremath{\mathtt{n}}^2$ bits of memory. The implementation here uses a matrix of $ \mathtt{bool}$ values so it actually uses on the order of $ \ensuremath{\mathtt{n}}^2$ bytes of memory. A more careful implementation, that packs $ \mathtt{w}$ boolean values into each word of memory could reduce this space usage to $ O(\ensuremath{\mathtt{n}}^2/\ensuremath{\mathtt{w}})$ words of memory.

Theorem 12..1   The $ \mathtt{AdjacencyMatrix}$ data structure implements the $ \mathtt{Graph}$ interface. An $ \mathtt{AdjacencyMatrix}$ supports the operations The space used by an $ \mathtt{AdjacencyMatrix}$ is $ O(\ensuremath{\mathtt{n}}^2)$.

Despite the high memory usage and poor performance of the $ \mathtt{inEdges(i)}$ and $ \mathtt{outEdges(i)}$ operations, an $ \mathtt{AdjacencyMatrix}$ can still be useful for some applications. In particular, when the graph $ G$ is dense, i.e., it has close to $ \ensuremath{\mathtt{n}}^2$ edges, then a memory usage of $ \ensuremath{\mathtt{n}}^2$ may be acceptable.

The $ \mathtt{AdjacencyMatrix}$ data structure is also commonly used because algebraic operations on the matrix $ \mathtt{a}$ can be used to efficiently compute properties of the graph $ G$. This is a topic for a course on algorithms, but we point out one such property here: If we treat the entries of $ \mathtt{a}$ as integers (1 for $ \mathtt{true}$ and 0 for $ \mathtt{false}$) and multiply $ \mathtt{a}$ by itself using matrix multiplication then we get the matrix $ \ensuremath{\mathtt{a}}^2$. Recall, from the definition of matrix multiplication, that

$\displaystyle \ensuremath{\mathtt{a^2[i][j]}} = \sum_{k=0}^{\ensuremath{\mathtt...
...1} \ensuremath{\mathtt{a[i][k]}}\cdot \ensuremath{\mathtt{a[k][j]}} \enspace .
$

Interpreting this sum in terms of the graph $ G$, this formula counts the number of vertices, $ \ensuremath{\mathtt{k}}$, such that $ G$ contains both edges $ \mathtt{(i,k)}$ and $ \mathtt{(k,j)}$. That is, it counts the number of paths from $ \ensuremath{\mathtt{i}}$ to $ \ensuremath{\mathtt{j}}$ (through intermediate vertices, $ \ensuremath{\mathtt{k}}$) that have length exactly 2. This observation is the foundation of an algorithm that computes the shortest paths between all pairs of vertices in $ G$ using only $ O(\log \ensuremath{\mathtt{n}})$ matrix multiplications.

opendatastructures.org