Algorithms in a Nutshell

Overview | 139

Graph

Algorithms

In Figure 6-5, a cycle exists in the path <v 3 ,v 1 ,v 5 ,v 4 ,v 2 ,v 1 ,v 5 ,v 4 ,v 2 >, and this cycle

is best represented by the notation <v 1 ,v 5 ,v 4 ,v 2 ,v 1 >. Note that in the directed,

weighted graph in Figure 6-2, there is a cycle < v 3 ,v 5 ,v 3 >.

When using an adjacency list to store an undirected graph, the same edge (u,v)

appears twice—once in the linked list of neighbor vertices foruand once forv.

Thus the storage of undirected graphs in an adjacency list is twice as much as for a

directed graph with the same number of vertices and edges. When using an adja-

cency matrix to store an undirected graph, you must ensure that the entry

A[i][j]=A[j][i]; no additional storage is necessary.

Storage Issues

There are several observations to make when using a two-dimensional matrix to

represent potential relationships amongnelements in a set. First, the matrix

requiresn^2 elements of storage, yet there are times when the number of relation-

ships is much smaller. In these cases—known assparsegraphs—it may be

impossible to store large graphs with more than several thousand vertices because

of the limitations of computer memory. For example, using the standard Java

virtual machine heap size of 256MB, creating a two-dimensional matrixnew

int[4096][4096] exceeds the available memory. Although one can execute

programs on computers with more available memory, it is a fact that there is a

fixed upper size beyond which no matrix can be constructed. Additionally,

traversing through large matrices to locate the few edges in sparse graphs becomes

costly, and this storage representation prevents efficient algorithms from

achieving their true potential. Second, matrices are unsuitable when there may be

multiple relationships between a pair of elements. To store these relationships in a

matrix, each element would become a list, and the abstraction ofA[i][j] being the

ijth element breaks.

Figure 6-4. Adjacency matrix representation of directed, weighted graph

Figure 6-5. Sample undirected graph

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use