The adjacency list representation of a graph provides a compact way to represent sparse graphs, for example, those for which |E| is much less than |V|². Even though it is a representation that is useful for a lot of algorithms (which we will visit later), it does not support some features. For example, one cannot quickly tell whether there is an edge connecting two given vertices. In order to determine if u and v are connected, one has to go through the adjacency list of u to find an edge connecting it to v. Since the adjacency list of u can have at most E edges, this procedure runs in O(E) time. One alternative representation that remedies this disadvantage at the cost of using asymptotically more memory is the adjacency matrix representation.

In this representation, a graph G = (V, E) is represented by a |V| x |V| matrix A = (a_ij), where a_ij equals 1 if there's an edge (i, j) and 0 otherwise. The following table shows the adjacency matrix representation of the directed graph of Figure 6.1:

The following table shows the adjacency matrix representation of the undirected graph of Figure 6.2:

The adjacency matrix representation of a graph requires O(V²) memory, independent of the number of edges in the graph. One thing to note on the adjacency matrix representation of undirected graphs is that the matrix is symmetrical along the main diagonal, since (u, v) and (v, u) represent the same edge. As such, the adjacency matrix of an undirected graph is its own transpose (A = A^T). Taking advantage of this symmetry, one can cut on the memory needed to store the graph almost in half, as you don't need the array of each vertex to have size V. If i tracks the index of vertices in V, the size of array[i] can decrease by one as i increases by one.

The following code shows how to create a graph using the adjacency matrix representation in Java:

public class AdjacencyMatrixGraph {
  int[][] adj;
  public AdjacencyMatrixGraph(int nodes) {
    this.adj = new int[nodes][nodes];
  }
  public void addEdge(int u, int v) {
    this.adj[u][v] = 1;
  }
}  

The adjacency matrix representation is also robust enough to support different graph variants. In order to support weighted graphs, for example, one can store the weight of the edge in a_ij, instead of just one. The adjacency list representation is asymptotically at least as space-efficient as the adjacency matrix representation, but adjacency matrices are simpler, so they might be preferable when the graphs are reasonably small or dense. As previously stated, a sparse graph is one in which |E| is much less than |V|², whereas a dense graph is one in which |E| is closer to |V|². The adjacency list representation is more memory-efficient for sparse graphs. For dense graphs, an adjacency matrix representation is better suited, as it possibly takes less memory due to list pointers.