Previous    Next

An adjacency-matrix representation of a graph is a V-by-V matrix of Boolean values, with the entry in row v and column w defined to be 1 if there is an edge connecting vertex v and vertex w in the graph, and to be 0 otherwise. Screenshot depicts an example.

This Boolean matrix is another representation of the graph depicted in Screenshot. It has a 1 (true) in row v and column w if there is an edge connecting vertex v and vertex w and a 0 (false) in row v and column w if there is no such edge. The matrix is symmetric about the diagonal. For example, the sixth row (and the sixth column) says that vertex 6 is connected to vertices 0 and 4. For some apps, we will adopt the convention that each vertex is connected to itself, and assign 1s on the main diagonal. The large blocks of 0s in the upper right and lower left corners are artifacts of the way we assigned vertex numbers for this example, not characteristic of the graph (except that they do indicate the graph to be sparse).

Program 17.7 is an implementation of the graph ADT interface that uses a direct representation of this matrix, built as a array of arrays, as depicted in Screenshot. It is a two-dimensional existence table with the entry adj[v][w] set to true if there is an edge connecting v and w in the graph, and set to false otherwise. Note that maintaining this property in an undirected graph requires that each edge be represented by two entries: the edge v-w is represented by true values in both adj[v][w] and adj[w][v], as is the edge w-v.

##### Screenshot Adjacency matrix data structure

This figure depicts the Java representation of the graph in Screenshot, as an array of arrays (with 0 and 1 representing false and true, respectively).

This implementation is more suited for dense graphs than for sparse ones, so in some contexts we might wish to explictly distinguish it from other implementations. For example, we might use a wrapper class DenseGraph to make this distinction explicit.

This class implements the interface in Program 17.1, using an array of Boolean arrays to represent the graph (see Screenshot). Edges are inserted and removed in constant time. Duplicate edge insert requests are silently ignored, but clients can use edge to test whether an edge exists. Constructing the graph takes time proportional to V2.

class Graph
{
private int Vcnt, Ecnt;
private boolean digraph;
Graph(int V, boolean flag)
{
Vcnt = V; Ecnt = 0; digraph = flag;
}
int V() { return Vcnt; }
int E() { return Ecnt; }
boolean directed() { return digraph; }
void insert(Edge e)
{ int v = e.v, w = e.w;
}
void remove(Edge e)
{ int v = e.v, w = e.w;
}
boolean edge(int v, int w)
// Program 17.8
}

This implementation of the iterator for Program 17.7 uses an index i to scan past false entries in row v of the adjacency matrix (adj[v]). An invocation of beg() followed by a sequence of invocations of nxt() (checking that end() is false before each invocation) gives a sequence of the vertices adjacent to v in G in order of their vertex index.

{
private int i, v;
{ this.v = v; i = -1;}
public int beg()
{ i = -1; return nxt(); }
public int nxt()
{
for (i++; i < V(); i++)
if (edge(v, i) == true) return i;
return -1;
}
public boolean end()
{ return i >= V(); }
}

#### Exercises

17.17 Give the adjacency-matrix representations of the three graphs depicted in Screenshot.

17.18 Give an implementation of show for the representation-independent GraphIO class of Program 17.4 that prints out a two-dimensional matrix of 0s and 1s like the one illustrated in Screenshot. Note: You cannot depend upon the iterator producing vertices in order of their indices.

Given a graph, consider another graph that is identical to the first, except that the names of (integers corresponding to) two vertices are interchanged. How are the adjacency matrices of these two graphs related?

17.20 Add operations to the graph ADT that allow clients to insert and delete vertices, and provide implementations for the adjacency-matrix representation.

17.21 Modify Program 17.7 to cut its space requirements about in half by not including array entries a[v][w] for w greater than v.

Modify Program 17.7 to ensure that, if your computer has B bits per word, a graph with V vertices is represented in about V2/B words (as opposed to V2). Do empirical tests to assess the effect of packing bits into words on the time required for the ADT operations.

Describe what happens if there is insufficient memory available to represent the matrix when the constructor in Program 17.7 is invoked, and suggest appropriate modifications to the code to handle this situation.

Develop a version of Program 17.7 that uses a single array with V2 entries.

17.25 Suppose that all k vertices in a group have consecutive indices. How can you determine from the adjacency matrix whether or not that group of vertices constitutes a clique? Write a client ADT operation that finds, in time proportional to V2, the largest group of vertices with consecutive indices that constitutes a clique.