Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Adjacency Matrices

Consider a directed graph tex2html_wrap_inline71355 with n vertices, tex2html_wrap_inline71661. The simplest graph representation scheme uses an tex2html_wrap_inline68887 matrix A of zeroes and ones given by

displaymath71647

I.e., the tex2html_wrap_inline61089 element of the matrix, is a one only if tex2html_wrap_inline71669 is an edge in G. The matrix A is called an adjacency matrix  .

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

displaymath71648

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 and incident on a given vertex. E.g., consider vertex tex2html_wrap_inline71521. Each one in the tex2html_wrap_inline58387 row corresponds to an edge that emanates from vertex tex2html_wrap_inline71521. Conversely, each one in the tex2html_wrap_inline58387 column corresponds to an edge incident on vertex tex2html_wrap_inline71521.

We can also use adjacency matrices to represent undirected graphs. I.e., we represent an undirected graph tex2html_wrap_inline71355 with n vertices, using an tex2html_wrap_inline68887 matrix A of zeroes and ones given by

displaymath71649

Since the two sets tex2html_wrap_inline71695 and tex2html_wrap_inline71697 are equivalent, matrix A is symmetric about the diagonal. I.e., tex2html_wrap_inline71701. Furthermore, all of the entries on the diagonal are zero. I.e., tex2html_wrap_inline71703 for tex2html_wrap_inline69739.

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

displaymath71650

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_inline68887 matrix A in which the tex2html_wrap_inline68907 is the numeric label associated with edge tex2html_wrap_inline71715 in the case of a directed graph, and edge tex2html_wrap_inline71695, in an undirected graph.

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

displaymath71651

In this case, the array entries corresponding to non-existent edges have all been set to tex2html_wrap_inline69187. Here tex2html_wrap_inline69187 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_inline69187 is much like one that does not exist.

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


next up previous contents index

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