The most popular and convenient representation of a graph, whether
directed or undirected, weighted or unweighted, is an *adjacency
matrix*. The graph is represented by a matrix whose rows and
columns are indexed by the nodes. There is an entry in the matrix in
row N1, column N2, iff there is an edge from N1 to N2 in the graph. In
a weighted graph, the matrix position (N1,N2) would contain the weight
of the edge from N1 to N2.

In the adjacency matrix for a directed graph the successors of node N are stored in row N and the predecessors for node N are stored in column N. For example:

Row `B' gives the successors of `B', column `B' gives predecessors of `B'. The fact that row `D' is empty indicates that `D' has no successors; similarly, column `A' being empty indicates `A' has no predecessors.

Certain operations are extremely efficient with an adjacency matrix representation:

- adding or deleting an edge
- adding or deleting a node (= adding/deleting a row and column)

In fact, we have already discussed the solution to this problem. When a graph has very few - O(N) - edges, almost all the positions in the matrix will be zero (empty). Does anyone recall an efficient implementation of almost-empty matrices we discussed several lectures ago?

A matrix in which most of the positions are zero is called a *sparse
matrix*. We talked about these in our
lecture about
multi-linked lists. They can be represented very efficiently by
having each row be a linked list, and each column a linked list, where
the rows and columns *share* nodes. You only allocate space for
the *non*-empty positions of the matrix. The matrix above would
be represented in this way:

The space needed is O(N+E) - there are 2N list headers and one node in the matrix for each

This representation is commonly called the *adjacency list*
representation. Often, for simplicity of implementation, the successor
and predecessor lists do not share nodes but have separate, redundant
nodes. If the graph is undirected, the predecessor and successor lists
will be identical so only one of them is necessary.

The biggest drawback of this representation is that deleting an edge, or even looking up its weight, is O(E) time, not constant-time as it is with an adjacency matrix.