Algorithms in a Nutshell

Overview | 141

Graph

Algorithms

Data Structure Design

The UML diagram in Figure 6-6 represents the core functionality we expect for

graphs in this chapter; see Chapter 3 for details on UML diagrams. The C++

Graphclass stores a (directed or undirected) graph using an adjacency list repre-

sentation implemented with core classes from the C++ Standard Template

Library (STL). Specifically, it stores the information as an array oflists, onelist

for each vertex. For each vertexuthere is alistofIntegerPairobjects repre-

senting the edge (u,v) of weightw.

Table 6-1. Performance comparison of two algorithm variations

Graph type O((V+E)*logV) Comparison O(V^2 +E)

Sparse graph:

E is O(V)

O(V logV) is smaller than O(V^2 )

Break-even graph:

E is O(V^2 /logV)

O(V^2 +V*logV) = O(V^2 ) is equivalent to O(V^2 +V^2 /logV) = O(V^2 )

Dense graph:

E is O(V^2 )

O(V^2 logV) is larger than O(V^2 )

Figure 6-6. Core graph operations

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