Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Adjacency Matrices

Consider a directed graph tex2html_wrap_inline69997 with n vertices, tex2html_wrap_inline70303. The simplest graph representation scheme uses an tex2html_wrap_inline67605 matrix A of zeroes and ones given by

displaymath70289

That is, the tex2html_wrap_inline59950 element of the matrix, is a one only if tex2html_wrap_inline70311 is an edge in G. The matrix A is called an adjacency matrix  .

For example, the adjacency matrix for graph tex2html_wrap_inline70091 in Figure gif is

displaymath70290

Clearly, the number of ones in the adjacency matrix is equal to the number of edges in the graph.

One advantage of using an adjacency matrix is that it is easy to determine the sets of edges emanating from a given vertex. For example, consider vertex tex2html_wrap_inline70163. Each one in the tex2html_wrap_inline57340 row corresponds to an edge that emanates from vertex tex2html_wrap_inline70163. Conversely, each one in the tex2html_wrap_inline57340 column corresponds to an edge incident on vertex tex2html_wrap_inline70163.

We can also use adjacency matrices to represent undirected graphs. That is, we represent an undirected graph tex2html_wrap_inline69997 with n vertices, using an tex2html_wrap_inline67605 matrix A of zeroes and ones given by

displaymath70291

Since the two sets tex2html_wrap_inline70337 and tex2html_wrap_inline70339 are equivalent, matrix A is symmetric about the diagonal. That is, tex2html_wrap_inline70343. Furthermore, all of the entries on the diagonal are zero. That is, tex2html_wrap_inline70345 for tex2html_wrap_inline68455.

For example, the adjacency matrix for graph tex2html_wrap_inline70245 in Figure gif is

displaymath70292

In this case, there are twice as many ones in the adjacency matrix as there are edges in the undirected graph.

A simple variation allows us to use an adjacency matrix to represent an edge-labeled graph. For example, given numeric edge labels, we can represent a graph (directed or undirected) using an tex2html_wrap_inline67605 matrix A in which the tex2html_wrap_inline67625 is the numeric label associated with edge tex2html_wrap_inline70357 in the case of a directed graph, and edge tex2html_wrap_inline70337, in an undirected graph.

For example, the adjacency matrix for the graph tex2html_wrap_inline70275 in Figure gif is

displaymath70293

In this case, the array entries corresponding to non-existent edges have all been set to tex2html_wrap_inline67905. Here tex2html_wrap_inline67905 serves as a kind of sentinel . The value to use for the sentinel depends on the application. For example, if the edges represent routes between geographic locations, then a route of length tex2html_wrap_inline67905 is much like one that does not exist.

Since the adjacency matrix has tex2html_wrap_inline70283 entries, the amount of spaced needed to represent the edges of a graph is tex2html_wrap_inline70371, regardless of the actual number of edges in the graph. If the graph contains relatively few edges, e.g., if tex2html_wrap_inline70373, then most of the elements of the adjacency matrix will be zero (or tex2html_wrap_inline67905). A matrix in which most of the elements are zero (or tex2html_wrap_inline67905) is a sparse matrix  .


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.